Submission #1086241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086241		4QT0R	Examination (JOI19_examination)	C++17	100 / 100	340 ms	41104 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

struct event{
	int x;
	int x2;
	int y;
	int y2;
	int typ;
};

event pts[400003];

void init(int &n, int &q){
	cin >> n >> q;
	set<int> s;
	map<int,int> mp;
	for (int i = 1; i<=n; i++){
		cin >> pts[i].x >> pts[i].y;
		pts[i].x2=pts[i].x+pts[i].y;
		s.insert(pts[i].y);
	}
	for (int i = n+1; i<=n+q; i++){
		cin >> pts[i].x >> pts[i].y >> pts[i].y2;
		pts[i].x2=max(pts[i].y2,pts[i].x+pts[i].y);
		pts[i].y2=max(pts[i].y,pts[i].y2-pts[i].x);
		pts[i].typ=1;
		s.insert(pts[i].y);
		s.insert(pts[i].y2);
	}
	int iter=0;
	for (auto u : s){
		mp[u]=iter++;
	}
	for (int i = 1; i<=n; i++)pts[i].y=mp[pts[i].y];
	for (int i = n+1; i<=n+q; i++){
		pts[i].y=mp[pts[i].y];
		pts[i].y2=mp[pts[i].y2];
	}
}

int ans[100002];
vector<pii> zap;

const int base=1<<19;
int tree[2*base];
void change(int v){
	v+=base;
	while(v){
		tree[v]++;
		v>>=1;
	}
}
int sum(int a, int b){
	a+=base-1;
	b+=base+1;
	int wyn=0;
	while(a/2!=b/2){
		if (!(a&1))wyn+=tree[a+1];
		if (b&1)wyn+=tree[b-1];
		a>>=1;
		b>>=1;
	}
	return wyn;
}

bool sorting(pii a, pii b){
	if (a.first==b.first)return a.second<b.second;
	return a.first>b.first;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,q;
	init(n,q);
	for (int i = 1; i<=n+q; i++){
		zap.push_back({pts[i].x,i});
	}
	sort(zap.begin(),zap.end(),sorting);
	for (auto [x0,ind] : zap){
		if (pts[ind].typ==0)change(pts[ind].y);
		else ans[ind-n]+=sum(pts[ind].y2+1,base-2);
	}
	fill(tree,tree+2*base,0);
	zap.clear();
	for (int i = 1; i<=n+q; i++){
		zap.push_back({pts[i].x2,i});
	}
	sort(zap.begin(),zap.end(),sorting);
	for (auto [x0,ind] : zap){
		if (pts[ind].typ==0)change(pts[ind].y);
		else ans[ind-n]+=sum(pts[ind].y,pts[ind].y2);
	}
	for (int i = 1; i<=q; i++)cout << ans[i] << '\n';
}

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