#include <bits/stdc++.h>
using namespace std;
#define int long long
#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 "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)))
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{
struct oo;
typedef oo* id;
struct oo{
id L,R,P;
int S,V;
};
id F,G;
void build(){
F=new oo;
F->S=F->V=0;
F->P=F->L=F->R=F;
G=F;
}
id init(int x){
id y=new oo;
y->P=y->L=y->R=F;
y->S=1; y->V=x;
return y;
}
void down(id x){x->S=x->L->S+x->R->S+1;}
void lef(id p,id u){p->L=u,u->P=p;}
void rig(id p,id u){p->R=u,u->P=p;}
void up(id x){
id y=x->P, z=y->P;
if(y->L==x) lef(y,x->R),rig(x,y);
else rig(y,x->L),lef(x,y);
if(z->L==y) lef(z,x);
else rig(z,x);
down(x),down(y);
}
void splay(id x){
for(;;){
id y=x->P,z=y->P;
if(y==F) return;
if(z!=F) if((z->L==y)==(y->L==x)) up(y);
else up(x);
up(x);
}
}
id pos(id x,int i){
if(x==F) return x;
if(x->L->V>=i) return pos(x->L,i);
if(x->V<i) return pos(x->R,i);
return x;
}
void dfs(id x,id y){
if(x==F) return;
if(x->V<y->V){
if(x->R==F) rig(x,y);
else dfs(x->R,y);
}
else{
if(x->L==F) lef(x,y);
else dfs(x->L,y);
}
down(x);
}
void add(int x){
id y=init(x);
dfs(G,y);
splay(y);
G=y;
}
int get(int x){
id tmp=pos(G,x);
if(tmp==F) return 0;
return tmp->R->S + 1;
}
}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(){
//freopen("EXAMiNATION.inp","r",stdin);
//freopen("EXAMiNATION.out","w",stdout);
n=in,q=in;
forinc(i,1,n){
int x=in,y=in; a[i]={x,y,x+y}; val.pb(x);
}
forinc(i,1,q) t[i]={in,in,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;});
forinc(i,1,val.size()) T[i].build();
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) cout<<ans[i]<<"\n";
}
Compilation message
examination.cpp: In member function 'void CTDL::splay(CTDL::id)':
examination.cpp:67:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(z!=F) if((z->L==y)==(y->L==x)) up(y);
^
examination.cpp: In function 'long long int que(long long int, long long int)':
examination.cpp:111:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<=val.size();i+=i&-i) ret+=T[i].get(x);
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3023 ms |
48836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3023 ms |
48836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
