Submission #378167

#	Time	Username	Problem	Language	Result	Execution time	Memory
378167		emanIaicepsa	Examination (JOI19_examination)	C++14	100 / 100	634 ms	12628 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define all(n) (n).begin(),(n).end()
#define mem(n,x) memset(n,x,sizeof(n))
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define pii pair<ll,ll>
#define vi vector<ll>
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename A> void _do(A x){ cerr<<x<<"\n"; }
template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}

int N, Q, ans[200005];

struct point{
	int x, y, z, id;
} arr[200005];

bool xcmp(point &a, point &b){
	if(a.x != b.x) return a.x > b.x;
	if(a.y != b.y) return a.y > b.y;
	if(a.z != b.z) return a.z > b.z;
	return a.id < b.id;
}

bool ycmp(point &a, point &b){
	if(a.y != b.y) return a.y > b.y;
	if(a.z != b.z) return a.z > b.z;
	return a.id < b.id;
}

int bit[200005];

void add(int x, int v){
	for(;x<=N+Q;x+=x&-x) bit[x] += v;
}

int query(int x){
	int ans = 0;
	for(;x;x-=x&-x) ans += bit[x];
	return ans;
}

void solve(int l, int r){
	if(l == r) return;
	int m = (l+r) / 2;
	solve(l, m);
	solve(m+1, r);
	sort(arr+l, arr+m+1, ycmp);
	sort(arr+m+1, arr+r+1, ycmp);
	
	int idx = l;
	for(int i=m+1;i<=r;i++){
		while(idx <= m && arr[idx].y >= arr[i].y){
			if(!arr[idx].id) add(arr[idx].z, 1);
			idx++;
		}
		if(arr[i].id) ans[arr[i].id] += query(N+Q) - query(arr[i].z - 1);
	}
	for(int i=l;i<idx;i++) if(!arr[i].id) add(arr[i].z, -1);
}

signed main(){
	IOS;
	cin >> N >> Q;
	for(int i=1;i<=N;i++) cin >> arr[i].x >> arr[i].y, arr[i].z = arr[i].x + arr[i].y, arr[i].id=0;
	for(int i=1;i<=Q;i++) cin >> arr[i+N].x >> arr[i+N].y >> arr[i+N].z, arr[i+N].id = i;
	
	vector<int> ax, ay, az;
	for(int i=1;i<=N+Q;i++) ax.pb(arr[i].x), ay.pb(arr[i].y), az.pb(arr[i].z);
	sort(all(ax)), sort(all(ay)), sort(all(az));
	ax.resize(unique(all(ax))-ax.begin());
	ay.resize(unique(all(ay))-ay.begin());
	az.resize(unique(all(az))-az.begin());
	for(int i=1;i<=N+Q;i++){
		arr[i].x = lower_bound(all(ax), arr[i].x) - ax.begin() + 1;
		arr[i].y = lower_bound(all(ay), arr[i].y) - ay.begin() + 1;
		arr[i].z = lower_bound(all(az), arr[i].z) - az.begin() + 1;
	}
	sort(arr+1, arr+1+N+Q, xcmp);


	solve(1, N+Q);
	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