제출 #755042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755042		Dan4Life	Examination (JOI19_examination)	C++17	0 / 100	342 ms	12452 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)

const int mxN = (int)6e5+10;
int n, q, fen[mxN], ans[mxN/6];
struct Query{ int x, y, z, i, t; };
struct Query2{ int y, z, i, t; };

vector<Query> A;

void upd(int x, int v){ for(; x<mxN; x+=x&-x) fen[x]+=v; }
int sum(int x){ int s=0;for(; x; x-=x&-x) s+=fen[x]; return s; }
int sum(int a, int b){ return (a<=b)*(sum(b)-sum(a-1)); }

void CDQ_Dnc(int l, int r){
	if(l==r) return;
	int mid = (l+r)>>1;
	vector<Query2> v; v.clear();
	for(int i = l; i <= r; i++){
		if(i<=mid and !A[i].t) v.pb({A[i].y,A[i].z,A[i].i,A[i].t});
		if(i>mid and A[i].t) v.pb({A[i].y,A[i].z,A[i].i,A[i].t});
	}
	sort(all(v), [&](Query2 a, Query2 b){return a.y>b.y;});
	vector<int> xd; xd.clear();
	for(auto [y,z,i,t] : v){
		if(!t) upd(z,1),xd.pb(z);
		else ans[i]+=sum(z,mxN-1);
	}
	for(auto u : xd) upd(u,-1);
	CDQ_Dnc(l,mid), CDQ_Dnc(mid+1,r);
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q; int x, y, z;
	vector<int> v; v.clear();
	for(int i = 0; i < n; i++){
		cin >> x >> y; z = x+y;
		v.pb(x), v.pb(y), v.pb(z);
		A.pb({x,y,z,i,0});
	}
	for(int i = 0; i < q; i++){
		cin >> x >> y >> z;
		v.pb(x), v.pb(y), v.pb(z);
		A.pb({x,y,z,i,1});
	}
	sort(all(v)); v.erase(unique(all(v)),end(v));
	for(auto &[x,y,z,i,t] : A){
		x = lower_bound(all(v),x)-begin(v)+1;
		y = lower_bound(all(v),y)-begin(v)+1;
		z = lower_bound(all(v),z)-begin(v)+1;
	}
	sort(all(A),[&](Query a, Query b){return a.x>b.x;}); CDQ_Dnc(0,n+q-1);
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

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