Submission #540946

#	Time	Username	Problem	Language	Result	Execution time	Memory
540946		krit3379	Examination (JOI19_examination)	C++17	100 / 100	187 ms	10904 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define N 100005

int fen[N],s[N],t[N],so[N],to[N],x[N],y[N],z[N],ans[N];
pair<int,int> p[N];
vector<pair<int,int>> q;

void update(int x,int k){
    while(x<N){
        fen[x]+=k;
        x+=x&-x;
    }
}

int sol(int x){
    int ans=0;
    while(x){
        ans+=fen[x];
        x-=x&-x;
    }
    return ans;
}

int main(){
    int n,m,i,k,now;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d %d",&s[i],&t[i]),p[i]={s[i],i},so[i]=s[i],to[i]=t[i];
    for(i=1;i<=m;i++)scanf("%d %d %d",&x[i],&y[i],&z[i]);
    sort(p+1,p+n+1);
    sort(so+1,so+n+1);
    sort(to+1,to+n+1);
    for(i=1;i<=m;i++)
        if(x[i]+y[i]>=z[i])q.push_back({x[i],i});
    sort(q.begin(),q.end());
    now=n;
    for(i=q.size()-1;i>=0;i--){
        while(now&&p[now].first>=q[i].first){
            update(lower_bound(to+1,to+n+1,t[p[now].second])-to,1);
            now--;
        }
        ans[q[i].second]=sol(n)-sol(lower_bound(to+1,to+n+1,y[q[i].second])-to-1);
    }
    q.clear();
    for(i=1;i<=n;i++)p[i]={s[i]+t[i],i};
    sort(p+1,p+n+1);
    for(i=1;i<=m;i++)
        if(x[i]+y[i]<z[i])q.push_back({z[i],i});
    sort(q.begin(),q.end());
    for(k=0;k<2;k++){
        for(i=0;i<=n;i++)fen[i]=0;
        now=n;
        for(i=q.size()-1;i>=0;i--){
            while(now&&p[now].first>=q[i].first){
                if(k)update(lower_bound(so+1,so+n+1,s[p[now].second])-so,1);
                else update(lower_bound(to+1,to+n+1,t[p[now].second])-to,1);
                now--;
            }
            if(k)ans[q[i].second]+=n-now;
            if(k)ans[q[i].second]-=sol(lower_bound(so+1,so+n+1,x[q[i].second])-so-1);
            else ans[q[i].second]-=sol(lower_bound(to+1,to+n+1,y[q[i].second])-to-1);
        }
    }
    for(i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(i=1;i<=n;i++)scanf("%d %d",&s[i],&t[i]),p[i]={s[i],i},so[i]=s[i],to[i]=t[i];
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:29:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for(i=1;i<=m;i++)scanf("%d %d %d",&x[i],&y[i],&z[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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