Submission #213250

#TimeUsernameProblemLanguageResultExecution timeMemory
213250zscoderExamination (JOI19_examination)C++17
100 / 100
329 ms14876 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int ans[124455];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<ii> v;
	vector<ii> v2;
	for(int i=0;i<n;i++)
	{
		int x,y; cin>>x>>y; v.pb({x,y}); v2.pb({x,x+y});
	}
	sort(v.begin(),v.end());
	sort(v2.begin(),v2.end());
	vector<pair<ii,int> > q1;
	vector<pair<ii,int> > q2;
	for(int i=0;i<q;i++)
	{
		int x,y,z; cin>>x>>y>>z;
		z=max(z,x+y);
		q2.pb({{x,z},i+1});
		q2.pb({{z-y,z},-(i+1)});
		q1.pb({{z-y,y},i+1});
	}
	sort(q1.rbegin(),q1.rend());
	sort(q2.rbegin(),q2.rend());
	int p=int(v.size())-1;
	int timer=0;
	pbds P;
	for(int z=0;z<q1.size();z++)
	{
		int x=q1[z].fi.fi; int y=q1[z].fi.se; int lab=q1[z].se;
		while(p>=0&&v[p].fi>=x)
		{
			P.insert(mp(v[p].se,++timer));
			p--;
		}
		int sign = (lab>0?1:-1);
		lab=abs(lab); lab--;
		int cnt = P.size() - P.order_of_key(mp(y,-10000));
		ans[lab]+=sign*cnt;
	}
	swap(q1,q2);
	P.clear();
	p=int(v2.size())-1;
	for(int z=0;z<q1.size();z++)
	{
		int x=q1[z].fi.fi; int y=q1[z].fi.se; int lab=q1[z].se;
		while(p>=0&&v2[p].fi>=x)
		{
			P.insert(mp(v2[p].se,++timer));
			p--;
		}
		int sign = (lab>0?1:-1);
		lab=abs(lab); lab--;
		int cnt = P.size() - P.order_of_key(mp(y,-10000));
		ans[lab]+=sign*cnt;
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z=0;z<q1.size();z++)
              ~^~~~~~~~~~
examination.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z=0;z<q1.size();z++)
              ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...