Submission #676642

#	Time	Username	Problem	Language	Result	Execution time	Memory
676642		browntoad	Examination (JOI19_examination)	C++14	0 / 100	537 ms	34492 KiB

examination

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define SQ(x) (x)*(x)
#define f first
#define s second
#define pii pair<int, int>
#define endl '\n'
#define pb push_back

const ll mod = 1e9+7;
const ll maxn = 6e5+5;
const ll inf = (1ll<<60);

ll pw(ll x, ll p){
    ll ret=1;
    while(p>0){
        if (p&1){
            ret*=x;
            ret%=mod;
        }
        x*=x;
        x%=mod;
        p>>=1;
    }
    return ret;
}
ll inv(ll x){
    return pw(x, mod-2);
}
vector<int> bit(maxn);
int query(int a){
    a=maxn-a-3;
    int ret=0;
    while(a>0){
        ret+=bit[a];
        a-=(a&-a);
    }
    return ret;
}
void modify(int a, int val){
    a=maxn-a-3;
    while(a<maxn){
        bit[a]+=val;
        a+=(a&-a);
    }
}
struct point{
    bool typ; // 0 is point, 1 is query
    int x, y, w;
    int id;
};
vector<point> vc;
vector<int> sol(200005);
int n, q;
vector<point> tmp;
bool cmp(point A, point B){
    if (A.w==B.w) return A.y<B.y;
    return A.w<B.w;
}
bool cmp2(point A, point B){
    if (A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}
void run(int l, int r){
    if (l>=r) return;
    if (vc[l].w==vc[r].w){
        tmp.clear();
        FOR(i, l, r+1){
            tmp.pb(vc[i]);
        }
        sort(ALL(tmp), cmp2);
        RREP(i, r-l+1){
            if (tmp[i].typ) {
                sol[tmp[i].id]+=query(tmp[i].y);
            }
            else {
                modify(tmp[i].y, 1);
            }
        }
        RREP(i, r-l+1){
            if (tmp[i].typ==0){
                modify(tmp[i].y, -1);
            }
        }
        return;
    }
    int mid = (vc[l].w+vc[r].w)>>1, pos=l-1;
    FOR(i, l, r+1){
        if (vc[i].w<=mid) pos=i;
    }
    run(l, pos);
    run(pos+1, r);
    tmp.clear();
    FOR(i, l, r+1){
        tmp.pb(vc[i]);
    }
    sort(ALL(tmp), cmp2);
    RREP(i, r-l+1){
        if (tmp[i].typ==0&&tmp[i].w>mid){
            modify(tmp[i].y, 1);
        }
        if (tmp[i].typ==1&&tmp[i].w<=mid){
            sol[tmp[i].id]+=query(tmp[i].y);
        }
    }
    RREP(i, r-l+1){
        if (tmp[i].typ==0&&tmp[i].w>mid){
            modify(tmp[i].y, -1);
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>q;
    vector<int> pos;
    REP(i, n){
        int x, y; cin>>x>>y;
        vc.pb({0, x, y, x+y, i});
        pos.pb(x);
        pos.pb(y);
        pos.pb(x+y);
    }
    REP(i, q){
        int x, y, c; cin>>x>>y>>c;
        vc.pb({1, x, y, c, i+n});
        pos.pb(x);
        pos.pb(y);
        pos.pb(c);
    }
    sort(ALL(pos));
    REP(i, n){
        vc[i].x=lower_bound(ALL(pos), vc[i].x)-pos.begin()+1;
        vc[i].y=lower_bound(ALL(pos), vc[i].y)-pos.begin()+1;
        vc[i].w=lower_bound(ALL(pos), vc[i].w)-pos.begin()+1;
    }
    REP(i, q){
        vc[i+n].x=lower_bound(ALL(pos), vc[i+n].x)-pos.begin()+1;
        vc[i+n].y=lower_bound(ALL(pos), vc[i+n].y)-pos.begin()+1;
        vc[i+n].w=lower_bound(ALL(pos), vc[i+n].w)-pos.begin()+1;
    }
    sort(ALL(vc), cmp);
    run(0, n+q-1);
    FOR(i, n, n+q){
        cout<<sol[i]<<endl;
    }
}

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