Submission #65693191

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#include <iomanip>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#include <iomanip>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const ll INF = 1e9+7;
const ll MOD = 998244353;
template <typename T> bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}
template <typename T> bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}
using namespace std;
typedef pair<int,int> pii;


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    int maxP = 2*N;
    vector<pair<int,int>> chords(M);
    vector<int> endpoints_cnt(maxP+2, 0), Bi_cnt(maxP+2, 0);
    for(int i=0;i<M;i++){
        int A, B;
        cin >> A >> B;
        chords[i] = {A, B};
        endpoints_cnt[A]++;
        endpoints_cnt[B]++;
        Bi_cnt[B]++;
    }
    vector<int> endpoints_ps(maxP+2,0), Bi_ps(maxP+2,0);
    for(int i=1;i<=maxP;i++){
        endpoints_ps[i] = endpoints_ps[i-1] + endpoints_cnt[i];
        Bi_ps[i] = Bi_ps[i-1] + Bi_cnt[i];
    }

    int Q;
    cin >> Q;
    struct Query{int C,D,idx,tot;};
    vector<Query> qs(Q);
    for(int i=0;i<Q;i++){
        int C,D;
        cin >> C >> D;
        qs[i] = {C, D, i, endpoints_ps[D-1] - endpoints_ps[C]};
    }

    sort(chords.begin(), chords.end(), [](auto &a, auto &b){
        return a.first < b.first;
    });
    vector<int> order(Q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){
        return qs[i].C < qs[j].C;
    });

    BIT bit(maxP+1);
    vector<int> ans(Q);
    int p = 0;
    for(int oi=0; oi<Q; oi++){
        int qi = order[oi];
        int C = qs[qi].C;
        int D = qs[qi].D;
        while(p < M && chords[p].first <= C){
            bit.add(chords[p].second, 1);
            p++;
        }
        int f = bit.sum(D-1);
        int inside = Bi_ps[D-1] - f;
        ans[qs[qi].idx] = qs[qi].tot - 2*inside;
    }

    for(int i=0;i<Q;i++){
        cout << ans[i] << endl;
    }
}

Submission Info

Judge Result