Submission #103288

#	Time	Username	Problem	Language	Result	Execution time	Memory
103288		LittleFlowers__	Examination (JOI19_examination)	C++14	100 / 100	1901 ms	66460 KiB

examination

#include <bits/stdc++.h>
using namespace std;
const int SZ=1<<10;
int ptr=SZ;
char buffer[SZ];
inline char readchar(){if(ptr==SZ){fread(buffer,1,SZ,stdin); ptr=0;}return buffer[ptr++];}
#define in ({int x=0;int c=readchar(),n=0;for(;!isdigit(c);c=readchar()) n=(c=='-');for(;isdigit(c);c=readchar()) x=x*10+c-'0';n?-x:x;})
inline void out(int 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 "EXAMiNATION"
#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)))

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N=100010;

int n,q;
struct tp{int x,y,z,i;}a[N],t[N];

int ans[N];
vector<int> val;


struct CTDL{
    ordered_set st; int sz=0;
    void add(int x){
        st.insert({x,++sz});
    }
    int get(int x){
        return st.size()-st.order_of_key({x,0});
    }
}T[N];


void upd(int i,int x){
    for(;i;i-=i&-i) T[i].add(x);
}
int que(int i,int x){
    i=lower_bound(all(val),i)-val.begin()+1;
    int ret=0;
    for(;i<=val.size();i+=i&-i) ret+=T[i].get(x);
    return ret;
}

signed main(){
    n=in,q=in;
    forinc(i,1,n){
        int x=in,y=in; a[i]={x,y+1,x+y}; val.pb(x);
    }
    forinc(i,1,q) t[i]={in,in+1,in,i};

    sort(all(val)); val.erase(unique(all(val)),val.end());
    forinc(i,1,n) a[i].x=lower_bound(all(val),a[i].x)-val.begin()+1;

    sort(a+1,a+n+1,[](tp i, tp j){return i.z>j.z;});
    sort(t+1,t+q+1,[](tp i, tp j){return i.z>j.z;});

    int j=1;
    forinc(i,1,q){
        while(j<=n && a[j].z>=t[i].z){
            upd(a[j].x,a[j].y); j++;
        }
        ans[t[i].i]=que(t[i].x,t[i].y);
    }
    forinc(i,1,q) out(ans[i]),putchar('\n');
}

Compilation message (stderr)

examination.cpp: In function 'int que(int, int)':
examination.cpp:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i) ret+=T[i].get(x);
          ~^~~~~~~~~~~~
examination.cpp: In function 'char readchar()':
examination.cpp:6:41: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 inline char readchar(){if(ptr==SZ){fread(buffer,1,SZ,stdin); ptr=0;}return buffer[ptr++];}
                                    ~~~~~^~~~~~~~~~~~~~~~~~~

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