Submission #468715

#	Time	Username	Problem	Language	Result	Execution time	Memory
468715		starplat	Examination (JOI19_examination)	C++14	0 / 100	1901 ms	33096 KiB

examination

#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> mp;
struct edge{
	ll a,b,c,id,ope;
}op[500005];
ll n,q,ct,ans[500005],x,y,z;
vector<ll> v;
void discretize()
{
	sort(v.begin(),v.end());
	for (int i=0;i<v.size();i++){
		if (!mp[v[i]]) mp[v[i]]=++ct;
	}
	for (int i=1;i<=n+q;i++){
		op[i].a=mp[op[i].a];
		op[i].b=mp[op[i].b];
		op[i].c=mp[op[i].c];
	}
}
int cmp(edge l,edge r)
{
	if (l.a!=r.a) return l.a>r.a;
	else if (l.b!=r.b) return l.b<r.b;
	else if (l.c<r.c) return l.c<r.c;
	else return l.id<r.id;
}
int cmp1(edge l,edge r)
{
	if (l.c!=r.c) return l.c>r.c;
	else if (l.b!=r.b) return l.b<r.b;
	else return l.id<r.id; 
}
ll t[1000005<<2];
void update(int id,int x,int y,int p,int v)
{
	if (x==y){
		t[id]+=v;
		return;
	}
	int mid=(x+y)/2;
	if (p<=mid) update(id*2,x,mid,p,v);
	else  update(id*2+1,mid+1,y,p,v);
	t[id]=t[id*2]+t[id*2+1];
}
ll query(int id,int x,int y,int l,int r)
{
	if (l<=x&&y<=r) return t[id];
	if (x>r||y<l) return 0;
	int mid=(x+y)/2;
	return query(id*2,x,mid,l,r)+query(id*2+1,mid+1,y,l,r);
}
void cdq(int l,int r)
{
	if (l>=r) return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);
	sort(op+l,op+r+1,cmp1);
	for (int i=l;i<=r;i++){
		if (op[i].id<=mid&&!op[i].ope) update(1,1,ct,op[i].b,1);
		if (op[i].id>mid&&op[i].ope) {
			ans[op[i].id-n]+=query(1,1,ct,1,op[i].b);
			//cout<<op[i].id-n<<" "<<query(1,1,ct,1,op[i].b)<<"\n";
		}
	}
	for (int i=l;i<=r;i++){
		if (op[i].id<=mid&&!op[i].ope) update(1,1,ct,op[i].b,-1);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++){
		cin>>op[i].a>>op[i].b;
		op[i].c=op[i].a+op[i].b;
		op[i].id=i;
		v.push_back(op[i].a);
		v.push_back(op[i].b);
		v.push_back(op[i].c);
	}
	for (int i=n+1;i<=n+q;i++){
		cin>>op[i].a>>op[i].b>>op[i].c;
		op[i].id=i,op[i].ope=1;
		v.push_back(op[i].a);
		v.push_back(op[i].b);
		v.push_back(op[i].c);
	}
	discretize();
	sort(op+1,op+1+n+q,cmp);
	for (int i=1;i<=n+q;i++) {
		cout<<op[i].ope<<" "<<op[i].id<<" "<<op[i].a<<" "<<op[i].b<<" "<<op[i].c<<"\n";
	}
	cdq(1,n+q);
	for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'void discretize()':
examination.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0;i<v.size();i++){
      |               ~^~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57