Submission #786446

#	Time	Username	Problem	Language	Result	Execution time	Memory
786446		winter0101	Examination (JOI19_examination)	C++14	100 / 100	2843 ms	201872 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct cla{
long long a,b,c;
}a[maxn];
struct query{
long long x,y,z;
}b[maxn];
vector<int>node[maxn*2];
vector<int>bit[maxn*2];
int n,q,m;
void fakeupdate(int x,int y,int val){
for (;x<=m;x+=(x-(x&(x-1)))){
    for(int z=y;z<=m;z+=(z-(z&(z-1)))){
        node[x].pb(z);
    }
}
}
void fakeget(int x,int y){
for (;x>=1;x-=(x-(x&(x-1)))){
    for(int z=y;z>=1;z-=(z-(z&(z-1)))){
        node[x].pb(z);
    }
}
}
void pre(){
for1(i,1,m){
sort(all(node[i]));
vector<int>::iterator it=unique(all(node[i]));
node[i].resize(distance(node[i].begin(),it));
bit[i].resize(sz(node[i]));
}
}
void update(int x,int y,int val){
for (;x<=m;x+=(x-(x&(x-1)))){
    for(int z=y;z<=m;z+=(z-(z&(z-1)))){
        int findpos=lower_bound(node[x].begin(),node[x].end(),z)-node[x].begin();
        bit[x][findpos]+=val;
    }
}
}
int get(int x,int y){
int sum=0;
for (;x>=1;x-=(x-(x&(x-1)))){
    for(int z=y;z>=1;z-=(z-(z&(z-1)))){
        int findpos=lower_bound(node[x].begin(),node[x].end(),z)-node[x].begin();
        sum+=bit[x][findpos];
    }
}
return sum;
}
vector<int>addpoint[maxn*2];
vector<int>answer[maxn*2];
int ans[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    m=n+q;
    vector<int>n1,n2,n3;
    n1.pb(1e9+1);
    n2.pb(1e9+1);
    n3.pb(2e9+1);
    for1(i,1,n){
    cin>>a[i].a>>a[i].b;
    n1.pb(a[i].a);
    n2.pb(a[i].b);
    n3.pb(a[i].a+a[i].b);
    a[i].c=a[i].a+a[i].b;
    }
    for1(i,1,q){
    cin>>b[i].x>>b[i].y>>b[i].z;
    n1.pb(b[i].x);
    n2.pb(b[i].y);
    n3.pb(b[i].z);
    }
    sort(all(n1),greater<int>());
    sort(all(n2),greater<int>());
    sort(all(n3),greater<int>());
    map<int,int>m1,m2,m3;
    for1(i,1,sz(n1)-1){
    if (n1[i]==n1[i-1])continue;
    m1[n1[i]]=m1[n1[i-1]]+1;
    }
    for1(i,1,sz(n2)-1){
    if (n2[i]==n2[i-1])continue;
    m2[n2[i]]=m2[n2[i-1]]+1;
    }
    for1(i,1,sz(n3)-1){
    if (n3[i]==n3[i-1])continue;
    m3[n3[i]]=m3[n3[i-1]]+1;
    }
    for1(i,1,n){
    a[i].a=m1[a[i].a];
    a[i].b=m2[a[i].b];
    a[i].c=m3[a[i].c];
    addpoint[a[i].a].pb(i);
    }
    for1(i,1,q){
    b[i].x=m1[b[i].x];
    b[i].y=m2[b[i].y];
    b[i].z=m3[b[i].z];
    answer[b[i].x].pb(i);
    }
    for1(i,1,m){
    for (auto v:addpoint[i]){
        fakeupdate(a[v].b,a[v].c,1);
    }
    for (auto v:answer[i]){
        fakeget(b[v].y,b[v].z);
    }
    }
    pre();
    for1(i,1,m){
    for (auto v:addpoint[i]){
        update(a[v].b,a[v].c,1);
    }
    for (auto v:answer[i]){
        ans[v]=get(b[v].y,b[v].z);
    }
    }
    /*cout<<"precal"<<'\n';
    for1(i,1,n){
    cout<<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<'\n';
    }
    cout<<'\n';
    for1(i,1,q){
    cout<<b[i].x<<" "<<b[i].y<<" "<<b[i].z<<'\n';
    }*/
    for1(i,1,q)cout<<ans[i]<<'\n';

}

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