#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=6e5+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;
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );
/** Read */
static const int buf_size = 4096;
inline int getChar() {
static char buf[buf_size];
static int len = 0, pos = 0;
if (pos == len) {
pos = 0, len = fread(buf, 1, buf_size, stdin);
}
if (pos == len) {
return -1;
}
return buf[pos++];
}
inline int readChar() {
int c = getChar();
while (c <= 32) {
c = getChar();
}
return c;
}
template <class T>
inline T readInt() {
int s = 1, c = readChar();
T x = 0;
if (c == '-')
s = -1, c = getChar();
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getChar();
return s == 1 ? x : -x;
}
/** Write */
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar( int x ) {
if (write_pos == buf_size)
fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt( T x, char end ) {
if (x < 0)
writeChar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
writeChar(s[n]);
if (end)
writeChar(end);
}
inline void writeWord( const char *s ) { while (*s)
writeChar(*s++); }
struct Flusher {
~Flusher() {
if (write_pos)
fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}
} flusher;
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++)
{
x[i]=readInt();
y[i]=readInt();
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++)
{
a[i]=readInt();
b[i]=readInt();
c[i]=readInt();
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);
}
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:154:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<vc.size();)
~^~~~~~~~~~
examination.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<vc.size();j++)
~^~~~~~~~~~
examination.cpp:179:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<qr[i].size();j++)
~^~~~~~~~~~~~~
examination.cpp:185: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 |
Execution timed out |
3044 ms |
253988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3077 ms |
270560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3077 ms |
270560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3044 ms |
253988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
