Submission #944613

#	Time	Username	Problem	Language	Result	Execution time	Memory
944613		pcc	Examination (JOI19_examination)	C++17	100 / 100	1567 ms	228248 KiB

examination

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

struct D{
	int x,y,id;
	D(){}
	D(int xx,int yy,int ii){
		x = xx,y = yy,id = ii;
	}
	bool operator<(D b)const{
		return (x+y==b.x+b.y?id>b.id:x+y<b.x+b.y);
	}
};

const int inf = 1e9;
const int mxn = 2e5+10;
vector<int> allx,ally;
vector<D> req;
int N,Q;
int ans[mxn];
pii range[mxn];
gp_hash_table<int,int> bit[mxn];

int getval(int x,int y){
	x = mxn-x-1,y = mxn-y-1;
	int re = 0;
	for(int tx = x;tx>0;tx-=tx&-tx){
		for(int ty = y;ty>0;ty -= ty&-ty){
			if(bit[tx].find(ty) == bit[tx].end())continue;
			re += bit[tx][ty];
		}
	}
	return re;
}
void modify(int x,int y){
	x = mxn-1-x,y = mxn-1-y;
	for(int i = x;i<mxn;i+=i&-i){
		for(int j = y;j<mxn;j+=j&-j)bit[i][j]++;
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	allx.push_back(-inf);
	ally.push_back(-inf);
	for(int i = 0;i<N;i++){
		int x,y;
		cin>>x>>y;
		req.push_back(D(x,y,-1));
		allx.push_back(x);
		ally.push_back(y);
	}
	for(int i = 1;i<=Q;i++){
		int a,b,c;
		cin>>a>>b>>c;
		range[i] = {a,b};
		allx.push_back(a);
		ally.push_back(b);
		req.push_back(D(c,0,i));
	}
#define _all(T) T.begin(),T.end()
	sort(_all(allx));allx.erase(unique(_all(allx)),allx.end());
	sort(_all(ally));ally.erase(unique(_all(ally)),ally.end());
	sort(req.begin(),req.end());
	for(auto it = req.rbegin();it != req.rend();it++){
		int x,y;
		if(it->id != -1){
			x = range[it->id].fs,y = range[it->id].sc;
		}
		else x = it->x,y = it->y;
		x = lower_bound(_all(allx),x)-allx.begin();
		y = lower_bound(_all(ally),y)-ally.begin();
		if(it->id != -1)ans[it->id] = getval(x,y);
		else modify(x,y);
	}
	for(int i = 1;i<=Q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

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