제출 #865967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865967		phoenix0423	Examination (JOI19_examination)	C++17	100 / 100	1421 ms	334812 KiB

examination

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int INF = 1e9;
int n, Q;
int ans[maxn];

struct info{
	int x, y, ttl, id;
	info(int _a, int _b, int _ttl, int _id = 0) : x(_a), y(_b), ttl(_ttl), id(_id){}
	bool operator < (const info& other) const{
		return ttl < other.ttl;
	}
};

vector<int> val, val2;
int getid(int x){
	return lower_bound(val.begin(), val.end(), x) - val.begin();
}
int getid2(int x){
	return lower_bound(val2.begin(), val2.end(), x) - val2.begin();
}

struct SGT{
	struct node{
		int val;
		node *l, *r;
		node() : val(0), l(nullptr), r(nullptr){}
	} *rt;
	void init(){rt = new node();}
	void upd(int pos, int val, node *&nd, int l, int r){
		if(!nd) nd = new node();
		nd->val += val;
		if(l == r) return;
		int m = (l + r) / 2;
		if(pos <= m) upd(pos, val, nd->l, l, m);
		else upd(pos, val, nd->r, m + 1, r);
	}
	void upd(int pos, int val){ upd(pos, val, rt, 0, maxn - 1);}
	int qry(int l, int r, node *nd, int L, int R){
		if(!nd) return 0;
		if(l > R || r < L) return 0;
		if(l <= L && r >= R) return nd->val;
		int m = (L + R) / 2;
		return qry(l, r, nd->l, L, m) + qry(l, r, nd->r, m + 1, R);
	}
	int qry(int l, int r){ return qry(l, r, rt, 0, maxn - 1);}
} BIT[maxn];

void upd(int x, int y, int val){
	x++, y++;
	while(x < maxn){
		BIT[x].upd(y, val);
		x += lowbit(x);
	}
}

int qry(int x, int y){
	x++, y++;
	int ret = 0;
	while(x > 0){
		ret += BIT[x].qry(0, y);
		x -= lowbit(x);
	}
	return ret;
}

int main(void){
	fastio;
	cin>>n>>Q;
	vector<info> a, q;
	for(int i = 0; i < n; i++){
		int x, y;
		cin>>x>>y;
		val.pb(x), val2.pb(y);
		a.pb(info(x, y, x + y));
	}
	for(int i = 0; i < Q; i++){
		int x, y, z;
		cin>>x>>y>>z;
		val.pb(x), val2.pb(y);
		q.pb(info(x, y, z, i));
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	sort(val2.begin(), val2.end());
	val2.erase(unique(val2.begin(), val2.end()), val2.end());
	sort(a.begin(), a.end());
	sort(q.begin(), q.end());
	for(int i = 0; i < maxn; i++) BIT[i].init();
	for(int i = 0; i < n; i++){
		a[i].x = getid(a[i].x), a[i].y = getid2(a[i].y);
		upd(a[i].x, a[i].y, 1);
	}
	int pos = 0;
	for(int i = 0; i < Q; i++){
		auto [x, y, z, id] = q[i];
		while(a[pos].ttl < z && pos < n) upd(a[pos].x, a[pos].y, -1), pos++;
		if(pos == n) break;
		x = getid(x), y = getid2(y);
		ans[id] = n - pos - qry(x - 1, maxn - 1) - qry(maxn - 1, y - 1) + qry(x - 1, y - 1);
	}
	for(int i = 0; i < Q; i++) cout<<ans[i]<<"\n";
	cout<<"\n";

}

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