oj.uz

Submission #121943

# Submission time Handle Problem Language Result Execution time Memory
121943 2019-06-27T09:00:27 Z MvC Examination (JOI19_examination) C++11
2 / 100
 3000 ms 552688 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=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++)
           ~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 423288 KB Output is correct
2 Correct 462 ms 423160 KB Output is correct
3 Correct 481 ms 423260 KB Output is correct
4 Correct 468 ms 423164 KB Output is correct
5 Correct 488 ms 423196 KB Output is correct
6 Correct 496 ms 423160 KB Output is correct
7 Correct 522 ms 426740 KB Output is correct
8 Correct 508 ms 426608 KB Output is correct
9 Correct 507 ms 426608 KB Output is correct
10 Correct 515 ms 426540 KB Output is correct
11 Correct 494 ms 426484 KB Output is correct
12 Correct 481 ms 424576 KB Output is correct
13 Correct 517 ms 426484 KB Output is correct
14 Correct 520 ms 426484 KB Output is correct
15 Correct 515 ms 426580 KB Output is correct
16 Correct 522 ms 426320 KB Output is correct
17 Correct 557 ms 426484 KB Output is correct
18 Correct 478 ms 424180 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 552688 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 3078 ms 552688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 423288 KB Output is correct
2 Correct 462 ms 423160 KB Output is correct
3 Correct 481 ms 423260 KB Output is correct
4 Correct 468 ms 423164 KB Output is correct
5 Correct 488 ms 423196 KB Output is correct
6 Correct 496 ms 423160 KB Output is correct
7 Correct 522 ms 426740 KB Output is correct
8 Correct 508 ms 426608 KB Output is correct
9 Correct 507 ms 426608 KB Output is correct
10 Correct 515 ms 426540 KB Output is correct
11 Correct 494 ms 426484 KB Output is correct
12 Correct 481 ms 424576 KB Output is correct
13 Correct 517 ms 426484 KB Output is correct
14 Correct 520 ms 426484 KB Output is correct
15 Correct 515 ms 426580 KB Output is correct
16 Correct 522 ms 426320 KB Output is correct
17 Correct 557 ms 426484 KB Output is correct
18 Correct 478 ms 424180 KB Output is correct
19 Execution timed out 3078 ms 552688 KB Time limit exceeded
20 Halted 0 ms 0 KB -