Submission #103546

#	Time	Username	Problem	Language	Result	Execution time	Memory
103546		LittleFlowers__	Examination (JOI19_examination)	C++14	100 / 100	638 ms	22864 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define task "exam"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int N=100010;
int n,m;
int ans[N];
struct id{
    int x,y,z,i;
}a[N],q[N];
vector<int> rr;
vector<int> bit[N],val[N];

int upp(const vector<int>&x,int y){
    return lower_bound(all(x),y)-x.begin()+1;
}

void add(int x,int y){
    int i=upp(rr,x);
    for(;i;i-=i&-i) val[i].pb(y);
}
void upd(int x,int y){
    int i=upp(rr,x);
    for(;i;i-=i&-i){
        int j=upp(val[i],y);
        for(;j;j-=j&-j) bit[i][j]++;
    }
}
int get(int x,int y){
    int ret=0;
    int i=upp(rr,x);
    for(;i<=rr.size();i+=i&-i){
        int j=upp(val[i],y);
        for(;j<bit[i].size();j+=j&-j) ret+=bit[i][j];
    }
    return ret;
}
main(){
    n=in,m=in;
    forinc(i,1,n){
        int x=in,y=in,z=x+y;
        a[i]={x,y,z};
        rr.pb(x);
    }
    forinc(i,1,m) q[i]={in,in,in,i};
    sort(all(rr)); rr.erase(unique(all(rr)),rr.end());

    forinc(i,1,n) add(a[i].x,a[i].y);

    forinc(i,1,n) sort(all(val[i])),bit[i].resize(val[i].size()+1);

    sort(a+1,a+n+1,[](id i,id j){return i.z>j.z;});
    sort(q+1,q+m+1,[](id i,id j){return i.z>j.z;});
    int j=1;
    forinc(i,1,m){
        while(j<=n && a[j].z>=q[i].z){
            upd(a[j].x,a[j].y); j++;
        }
        ans[q[i].i]=get(q[i].x,q[i].y);
    }
    forinc(i,1,m) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'int get(int, int)':
examination.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=rr.size();i+=i&-i){
          ~^~~~~~~~~~~
examination.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;j<bit[i].size();j+=j&-j) ret+=bit[i][j];
              ~^~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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