Submission #1213958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213958		Malix	Examination (JOI19_examination)	C++20	100 / 100	425 ms	41736 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int ft[600001],mx=599999;

void update(int x){
    x++;
    while(x<=600000){
        ft[x]++;
        x+=LSOne(x);
    }
}

int query(int x){
    x++;
    int ans=0;
    while(x){
        ans+=ft[x];
        x-=LSOne(x);
    }
    return ans;
}

int main() {   
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;cin>>n>>m;
    vector<pi> a(n),b(n),c(n);
    map<int,int> mp;
    vi arr,d;
    REP(i,0,n){
        int x,y;cin>>x>>y;
        a.PB({x,y});
        b.PB({x+y,x});
        c.PB({x+y,y});
        d.PB(-(x+y));
        arr.PB(x);arr.PB(y);arr.PB(x+y);
    }
    sort(a.begin(),a.end());sort(b.begin(),b.end());sort(c.begin(),c.end());sort(d.begin(),d.end());
    reverse(a.begin(),a.end());reverse(b.begin(),b.end());reverse(c.begin(),c.end());
    vi ans(m,0);
    vector<ti> X,Y,Z;
    REP(i,0,m){
        int x,y,z;cin>>x>>y>>z;
        if(x+y>=z)X.PB({x,y,i});
        else{
            Y.PB({z,x,i});
            Z.PB({z,y,i});
        }
        arr.PB(x);arr.PB(y);arr.PB(z);
    }
    sort(arr.begin(),arr.end());
    arr.erase(unique(arr.begin(),arr.end()),arr.end());
    REP(i,0,arr.size())mp[arr[i]]=i;
    sort(X.begin(),X.end());sort(Y.begin(),Y.end());sort(Z.begin(),Z.end());
    reverse(X.begin(),X.end());reverse(Y.begin(),Y.end());reverse(Z.begin(),Z.end());
    memset(ft,0,sizeof(ft));
    int pos=0;
    REP(i,0,X.size()){
        auto [x,y,z]=X[i];
        while(pos<n&&a[pos].F>=x)update(mp[a[pos++].S]);
        ans[z]=query(mx)-query(mp[y]-1);
    }
    memset(ft,0,sizeof(ft));
    int sz=Y.size();
    pos=0;
    REP(i,0,sz){
        auto [x,y,z]=Y[i];
        ans[z]=upper_bound(d.begin(),d.end(),-x)-d.begin();
        while(pos<n&&b[pos].F>=x)update(mp[b[pos++].S]);
        ans[z]-=query(mp[y]-1);
    }
    memset(ft,0,sizeof(ft));
    pos=0;
    REP(i,0,sz){
        auto [x,y,z]=Z[i];
        while(pos<n&&c[pos].F>=x)update(mp[c[pos++].S]);
        ans[z]-=query(mp[y]-1);
    }
    for(auto u:ans)cout<<u<<"\n";
}

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