#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,q,i,j,k,a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],rs[nmax],nr,sm[nmax],s;
order_set st[4*nmax];
vector<int>qr[nmax];
vector<pair<int,pair<int,int> > >qrr[nmax],vc;
pair<int,pair<int,int> >p;
void upd(int x,int l,int r,int p,int v)
{
st[x].in(mkp(v,nr));
if(l==r)return;
int mid=(l+r)/2;
if(p<=mid)upd(2*x,l,mid,p,v);
else upd(2*x+1,mid+1,r,p,v);
}
int qry(int x,int l,int r,int tl,int tr,int v)
{
if(l>tr || r<tl)return 0;
if(l>=tl && r<=tr)
{
v--;
//if(st[x].upper_bound(mkp(v,1e6))==st[x].end())return 0;
pair<int,int> y=*st[x].upper_bound(mkp(v,1e6));
int z=(int)st[x].size()-st[x].order_of_key(y);
return z;
}
int mid=(l+r)/2;
return qry(2*x,l,mid,tl,tr,v)+qry(2*x+1,mid+1,r,tl,tr,v);
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>q;
for(i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
vc.pb(mkp(x[i],mkp(0,i)));
vc.pb(mkp(y[i],mkp(1,i)));
vc.pb(mkp(x[i]+y[i],mkp(2,i)));
}
for(i=1;i<=q;i++)
{
cin>>a[i]>>b[i]>>c[i];
vc.pb(mkp(a[i],mkp(3,i)));
vc.pb(mkp(b[i],mkp(4,i)));
vc.pb(mkp(c[i],mkp(5,i)));
}
sort(vc.begin(),vc.end());
for(i=0;i<vc.size();)
{
k++;
for(j=i;j<vc.size();j++)
{
if(vc[j].fr!=vc[i].fr)break;
if(vc[j].sc.fr==2)sm[vc[j].sc.sc]=k;
else if(vc[j].sc.fr==1)y[vc[j].sc.sc]=k;
else if(vc[j].sc.fr==0)x[vc[j].sc.sc]=k;
else if(vc[j].sc.fr==3)a[vc[j].sc.sc]=k;
else if(vc[j].sc.fr==4)b[vc[j].sc.sc]=k;
else if(vc[j].sc.fr==5)c[vc[j].sc.sc]=k;
}
i=j;
}
for(i=1;i<=n;i++)
{
qr[sm[i]].pb(i);
//cout<<x[i]<<" "<<y[i]<<" "<<sm[i]<<endl;
}
for(i=1;i<=q;i++)
{
qrr[c[i]].pb(mkp(i,mkp(a[i],b[i])));
}
for(i=k;i>=1;i--)
{
for(j=0;j<qr[i].size();j++)
{
s=qr[i][j];
nr++;
upd(1,1,k,x[s],y[s]);
}
for(j=0;j<qrr[i].size();j++)
{
p=qrr[i][j];
rs[p.fr]=qry(1,1,k,p.sc.fr,k,p.sc.sc);
}
}
for(i=1;i<=q;i++)cout<<rs[i]<<'\n';
return 0;
}
Compilation message
examination.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
examination.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
examination.cpp: In function 'int main()':
examination.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<vc.size();)
~^~~~~~~~~~
examination.cpp:78:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<vc.size();j++)
~^~~~~~~~~~
examination.cpp:101:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<qr[i].size();j++)
~^~~~~~~~~~~~~
examination.cpp:107:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<qrr[i].size();j++)
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1797 ms |
423240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
515140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
515140 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1797 ms |
423240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
