oj.uz

Submission #121946

# Submission time Handle Problem Language Result Execution time Memory
121946 2019-06-27T09:06:34 Z MvC Examination (JOI19_examination) C++11
2 / 100
 3000 ms 381124 KB 
#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;
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--;
		auto it=st[x].upper_bound(mkp(v,1e6));
		if(it==st[x].end())return 0;
		pair<int,int> y=*it;
		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:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();)
          ~^~~~~~~~~~
examination.cpp:79:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i;j<vc.size();j++)
           ~^~~~~~~~~~
examination.cpp:102:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qr[i].size();j++)
           ~^~~~~~~~~~~~~
examination.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qrr[i].size();j++)
           ~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 254080 KB Output is correct
2 Correct 283 ms 254072 KB Output is correct
3 Correct 282 ms 254072 KB Output is correct
4 Correct 298 ms 254060 KB Output is correct
5 Correct 299 ms 254072 KB Output is correct
6 Correct 298 ms 254200 KB Output is correct
7 Correct 326 ms 257440 KB Output is correct
8 Correct 319 ms 257396 KB Output is correct
9 Correct 332 ms 257396 KB Output is correct
10 Correct 348 ms 257472 KB Output is correct
11 Correct 317 ms 257268 KB Output is correct
12 Correct 310 ms 255508 KB Output is correct
13 Correct 307 ms 257308 KB Output is correct
14 Correct 304 ms 257304 KB Output is correct
15 Correct 315 ms 257272 KB Output is correct
16 Correct 305 ms 257140 KB Output is correct
17 Correct 314 ms 257192 KB Output is correct
18 Correct 290 ms 255064 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 381124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 381124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 254080 KB Output is correct
2 Correct 283 ms 254072 KB Output is correct
3 Correct 282 ms 254072 KB Output is correct
4 Correct 298 ms 254060 KB Output is correct
5 Correct 299 ms 254072 KB Output is correct
6 Correct 298 ms 254200 KB Output is correct
7 Correct 326 ms 257440 KB Output is correct
8 Correct 319 ms 257396 KB Output is correct
9 Correct 332 ms 257396 KB Output is correct
10 Correct 348 ms 257472 KB Output is correct
11 Correct 317 ms 257268 KB Output is correct
12 Correct 310 ms 255508 KB Output is correct
13 Correct 307 ms 257308 KB Output is correct
14 Correct 304 ms 257304 KB Output is correct
15 Correct 315 ms 257272 KB Output is correct
16 Correct 305 ms 257140 KB Output is correct
17 Correct 314 ms 257192 KB Output is correct
18 Correct 290 ms 255064 KB Output is correct
19 Execution timed out 3044 ms 381124 KB Time limit exceeded
20 Halted 0 ms 0 KB -