Submission #954945

#	Time	Username	Problem	Language	Result	Execution time	Memory
954945		ByeWorld	Examination (JOI19_examination)	C++14	2 / 100	3065 ms	886692 KiB

examination

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 2e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int MOD = 998244353;

int maxy, maxz;

struct row {
	int l, r, mid, val;
	row *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2; mid = md;
		le = NULL; ri = NULL;
	}
	void bnc(){
		if(le==NULL){
			le = new row();
			le->bd(l, mid);
		}
		if(ri==NULL){
			ri = new row();
			ri->bd(mid+1, r);
		}
	}
	int que(int a, int b){
		// cout << l << ' '<< r << ' ' << " que\n";
		if(a<=l && r<=b) return val;
		if(r<a || b<l) return 0;
		bnc();
		return le->que(a, b) + ri->que(a, b);
	}
	int upd(int a, int p){
		if(l==r && l==a){
			val += p;
		// cout << l << ' '<< r << ' ' << val << " upd\n";
			return val;
		}
		if(a<l || r<a) return val;
		bnc();
		return val = le->upd(a, p) + ri->upd(a, p);
	}
};
struct seg {
	int l, r, mid;
	row *val;
	seg *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2; mid = md;
		val = new row();
		val->bd(1, maxz);
	}
	void bnc(){
		if(le==NULL){
			le = new seg();
			le->bd(l, mid);
		}
		if(ri==NULL){
			ri = new seg();
			ri->bd(mid+1, r);
		}
	}
	int que(int x, int y, int a, int b){
		if(x<=l && r<=y) return val->que(a, b);
		if(r<x || y<l) return 0;
		bnc();
		// cout << l << ' '<< r << " queluar\n";
		return le->que(x, y, a, b) + ri->que(x, y, a, b);
	}
	void upd(int x, int a, int p){
		if(l==r && l==x){
		// cout << l << ' '<< r << " lr_x\n";
			val->upd(a, p);
			return;
		}
		if(x<l || r<x) return;
		bnc();
		// cout << l << ' '<< r << " lr_x\n";
		val->upd(a, p); // segtree parentnya juga kena
		le->upd(x, a, p); ri->upd(x, a, p);
		return;
	}
} A;

int n, q;
vector <pii> vec;
vector <pair<pii,pii>> que;
vector <int> cc1, cc2;
int z[MAXN], y[MAXN], X[MAXN], Y[MAXN];
int ans[MAXN];

signed main() {
	cin >> n >> q;
	for(int i=1; i<=n; i++){
		cin >> X[i] >> Y[i];
		cc1.pb(Y[i]); cc2.pb(X[i]+Y[i]);
	}

	for(int i=1; i<=q; i++){
		int a, b, c; cin >> a >> b >> c;
		que.pb({{a, b}, {c, i}});
		// cc1.pb(b); cc2.pb(c);
	}
	sort(que.rbegin(), que.rend());

	cc1.pb(-1);
	sort(cc1.begin(), cc1.end());
	cc1.resize( unique(cc1.begin(), cc1.end()) - cc1.begin() );
	cc2.pb(-1);
	sort(cc2.begin(), cc2.end());
	cc2.resize( unique(cc2.begin(), cc2.end()) - cc2.begin() );

	for(int i=1; i<=n; i++){
		y[i] = lower_bound(cc1.begin(), cc1.end(), Y[i]) - cc1.begin();
		z[i] = lower_bound(cc2.begin(), cc2.end(), X[i]+Y[i]) - cc2.begin();
		vec.pb({X[i], i});
		maxy = max(maxy, y[i]);
		maxz = max(maxz, z[i]);
		// cout << i << ' ' << y[i] << ' ' << z[i] << " ins\n";
	}
	vec.pb({INF, INF});
	sort(vec.rbegin(), vec.rend());

	A.bd(1, maxy);
	int las = 1;
	for(int i=0; i<q; i++){
		int a = que[i].fi.fi, id = que[i].se.se;
		int b = lower_bound(cc1.begin(), cc1.end(), que[i].fi.se) - cc1.begin();
		int c = lower_bound(cc2.begin(), cc2.end(), que[i].se.fi) - cc2.begin();
		// cout << id << ' '<< b << ' ' << c << " que\n";
		while(las<=n && a <= vec[las].fi){
			int idx = vec[las].se;
			// cout << y[idx] << ' '<< z[idx] << " idxupd\n";
			A.upd(y[idx], z[idx], 1);
			las++;
		}
		ans[id] = A.que(b, maxy, c, maxz);
	}

	for(int i=1; i<=q; i++) cout << ans[i] << "\n"; //[i==q];
}

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