oj.uz

Submission #121945

# Submission time Handle Problem Language Result Execution time Memory
121945 2019-06-27T09:05:37 Z MvC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 550180 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--;
		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 473 ms 423072 KB Output is correct
2 Correct 496 ms 423284 KB Output is correct
3 Correct 511 ms 423236 KB Output is correct
4 Correct 496 ms 423252 KB Output is correct
5 Correct 480 ms 423160 KB Output is correct
6 Correct 467 ms 423160 KB Output is correct
7 Correct 510 ms 426740 KB Output is correct
8 Correct 499 ms 426568 KB Output is correct
9 Correct 504 ms 426724 KB Output is correct
10 Correct 510 ms 426484 KB Output is correct
11 Correct 496 ms 426560 KB Output is correct
12 Correct 502 ms 424564 KB Output is correct
13 Correct 514 ms 426508 KB Output is correct
14 Correct 521 ms 426528 KB Output is correct
15 Correct 510 ms 426376 KB Output is correct
16 Correct 492 ms 426228 KB Output is correct
17 Correct 485 ms 426484 KB Output is correct
18 Correct 472 ms 424028 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 423072 KB Output is correct
2 Correct 496 ms 423284 KB Output is correct
3 Correct 511 ms 423236 KB Output is correct
4 Correct 496 ms 423252 KB Output is correct
5 Correct 480 ms 423160 KB Output is correct
6 Correct 467 ms 423160 KB Output is correct
7 Correct 510 ms 426740 KB Output is correct
8 Correct 499 ms 426568 KB Output is correct
9 Correct 504 ms 426724 KB Output is correct
10 Correct 510 ms 426484 KB Output is correct
11 Correct 496 ms 426560 KB Output is correct
12 Correct 502 ms 424564 KB Output is correct
13 Correct 514 ms 426508 KB Output is correct
14 Correct 521 ms 426528 KB Output is correct
15 Correct 510 ms 426376 KB Output is correct
16 Correct 492 ms 426228 KB Output is correct
17 Correct 485 ms 426484 KB Output is correct
18 Correct 472 ms 424028 KB Output is correct
19 Execution timed out 3081 ms 550180 KB Time limit exceeded
20 Halted 0 ms 0 KB -