Submission #65670447

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT {
    int n;
    vector<int> f;
    BIT(int _n): n(_n), f(n+1,0){}
    void update(int i,int v){ for(;i<=n;i+=i&-i) f[i]+=v; }
    int query(int i){ int s=0; for(;i>0;i-=i&-i) s+=f[i]; return s; }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin>>N>>M;
    int L=2*N;
    vector<pair<int,int>> chords(M);
    for(int i=0;i<M;i++){
        cin>>chords[i].first>>chords[i].second;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    int n;
    vector<int> f;
    BIT(int _n): n(_n), f(n+1,0){}
    void update(int i,int v){ for(;i<=n;i+=i&-i) f[i]+=v; }
    int query(int i){ int s=0; for(;i>0;i-=i&-i) s+=f[i]; return s; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin>>N>>M;
    int L=2*N;
    vector<pair<int,int>> chords(M);
    for(int i=0;i<M;i++){
        cin>>chords[i].first>>chords[i].second;
    }
    vector<int> even_pref(L+1,0), bi_pref(L+1,0);
    for(auto &p:chords){
        even_pref[p.first]++;
        even_pref[p.second]++;
        bi_pref[p.second]++;
    }
    for(int i=1;i<=L;i++){
        even_pref[i]+=even_pref[i-1];
        bi_pref[i]+=bi_pref[i-1];
    }
    sort(chords.begin(), chords.end(), [](auto &a, auto &b){
        return a.first > b.first;
    });
    int Q;
    cin>>Q;
    struct Qry{int C,D,id; bool wrap;};
    vector<Qry> qs(Q);
    
    for(int i=0;i<Q;i++){
        cin>>qs[i].C>>qs[i].D;
        qs[i].id=i;
        qs[i].wrap = qs[i].C > qs[i].D;
    }
    sort(qs.begin(), qs.end(), [](auto &a, auto &b){
        return a.C > b.C;
    });
    
    BIT bit(L);
    vector<ll> ans(Q);
    int ptr=0, added=0;
    for(auto &q:qs){
        while(ptr<M && chords[ptr].first > q.C){
            bit.update(chords[ptr].second,1);
            ptr++;
            added++;
        }
        ll E;
        if(!q.wrap){
            E = even_pref[q.D-1] - even_pref[q.C];
            ll B = bit.query(q.D-1);
            ans[q.id] = E - 2*B;
        } else {
            E = (even_pref[L] - even_pref[q.C]) + even_pref[q.D-1];
            ll B_high = added;
            ll B_low = bi_pref[q.D-1];
            ll B = B_high + B_low;
            ans[q.id] = E - 2*B;
        }
    }
    for(int i=0;i<Q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Submission Info

Judge Result