Submission #331426

#	Time	Username	Problem	Language	Result	Execution time	Memory
331426		EIMONIM	Examination (JOI19_examination)	C++14	100 / 100	1115 ms	17972 KiB

examination

#include <bits/stdc++.h>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;

int MAXX = 0, MAXY = 0;
struct Node{
    int v=0;
    Node *lp=0, *rp=0;
    Node(){}
    void fix(){
        if (!lp) lp = new Node();
        if (!rp) rp = new Node();
    }
    void update(int i, int dx, int l, int r){
        if (r<=l) return ;
        if (l+1==r){
            v+=dx;
            return ;
        }
        int mid = (l+r)/2;
        fix();
        if (i<mid) lp->update(i,dx,l,mid);
        else rp->update(i,dx,mid,r);
        //cout<<"UPDATE1: "<<i<<" "<<l<<" "<<r<<(v - lp->v - rp->v)<<endl;
        v = lp->v + rp->v;
    }
    int query(int a, int b, int l, int r){
        if (a>r || b<l) return 0;
        //cout<<"QUERY1: "<<a<<" "<<v<<" "<<l<<" "<<r<<endl;
        if (a<=l && r<=b) return v;
        int res = 0, mid = (l+r)/2;
        if (lp) res += lp->query(a,b,l,mid);
        if (rp) res += rp->query(a,b,mid,r);
        return res;
    }
};
struct SEG{
    int n, sz;
    vector<int> a;
    SEG(int n=0): n(n){
        for(sz=1;sz<n;sz*=2);
        a.resize(2*sz);
    }
    void update(int i, int dx){
        a[i+=sz]+=dx;
        for(i/=2;i;i/=2) a[i] = a[2*i] + a[2*i+1];
    }
    int query(int l, int r){
        int res = 0;
        for(l+=sz, r+=sz; l<=r; l/=2, r/=2){
            if (l%2) res += a[l++];
            if (r%2==0) res += a[r--];
        }
        return res;
    }
};

bool cmp(pair<int, int> a, pair<int, int> b){
    return (a.first==b.first?a.second<b.second:a.first>b.first);
}
const int MAXN = 1e5 + 10;
int n,q;
int s[MAXN], t[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];
pair<int, int> vals[2*MAXN];

SEG seg;
void solve(int l, int r){
    if (r<=l+1) return ;
    int mid = (l+r)/2;
    //cout<<"HI: "<<l<<" "<<r<<endl;
    solve(l, mid);
    solve(mid, r);
    vector<pair<int, int>> eve;
    loop(i,l,mid) {
        int ind = vals[i].second;
        if(ind<n) eve.push_back({s[ind], ind});
    }
    loop(i,mid,r) {
        int ind = vals[i].second;
        if(ind>=n) eve.push_back({a[ind-n], ind});
    }
    sort(eve.begin(), eve.end());
    for(auto &e:eve){
        int i = e.second;
        if (i<n){
            seg.update(t[i], 1);
        }
        else{
            ans[i-n]+=seg.query(0, b[i-n]);
        }
    }
    for(auto &e:eve){
        int i = e.second;
        if (i<n){
            seg.update(t[i], -1);
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin>>n>>q;
    map<int, int> convs, convt;
    loop(i,0,n){
        cin>>s[i]>>t[i];
        vals[i] = {s[i]+t[i], i};
        convs[s[i]];
        convt[t[i]];
        //MAXX = max(MAXX, s[i]);
        //MAXY = max(MAXY, t[i]);
    }
    loop(i,0,q){
        cin>>a[i]>>b[i]>>c[i];
        vals[i+n] = {c[i], n+i};
        //MAXX = max(MAXX, a[i]);
        //MAXY = max(MAXY, b[i]);
    }
    convs[INF] = convt[INF];
    sort(vals, vals+n+q, cmp);
    //MAXX++, MAXY++;
    int cnt = 0;
    for(auto &p:convs) p.second = cnt++;
    for(auto &p:convs) p.second = cnt - p.second-1;
    MAXX = cnt, cnt = 0;
    for(auto &p:convt) p.second = cnt++;
    for(auto &p:convt) p.second = cnt - p.second-1;
    MAXY = cnt;
    loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
    loop(i,0,q) a[i] = convs.lower_bound(a[i])->second, b[i] = convt.lower_bound(b[i])->second;
    seg = SEG(MAXY);
    //sparsebit bit;
    solve(0, n+q);
    /*loop(ind, 0, n+q){
        int i = vals[ind].second;
        //cout<<"VALS: "<<vals[ind].first<<" "<<i<<" "<<i-n<<endl;
        if (i<n){ // point
            seg.update(s[i], t[i], 1, 0, MAXX);
            //bit.add(s[i], t[i]);
        }
        else{ // query
            i-=n;
            ans[i] = seg.query(0, a[i]+1, 0, b[i]+1, 0, MAXX);
            //ans[i] = bit.qry(a[i], b[i]);
        }
    }*/
    loop(i,0,q) cout<<ans[i]<<endl;
    return 0;
}
/*
color a
cls
g++ Examination.cpp -o a & a
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100





*/

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57