Submission #234085

#	Time	Username	Problem	Language	Result	Execution time	Memory
234085		wwdd	Examination (JOI19_examination)	C++14	100 / 100	978 ms	62964 KiB

examination

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef pair<pl,ll> tl;
vector<pl> w,qu,qp;
set<ll> bx,by;
map<ll,ll> mx,my;
class ST {
	private:
		vector<ll> st;
		int n;
	public:
		ST(int n_) {
			n = n_;
			st.assign(2*n,0);
		}
		void up(ll p, ll val) {
			p += n;
			st[p] += val;
			while(p > 1) {
				st[p>>1] = st[p] + st[p^1];
				p >>= 1;
			}
		}
		ll get(ll l, ll r) {
			l += n;r += n;
			ll res = 0;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {
					res += st[l];
					l++;
				}
				if(r&1) {
					r--;
					res += st[r];
				}
			}
			return res;
		}
		ll size() {
			return n;
		}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,q;
	cin >> n >> q;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		w.push_back({a,b});
		qp.push_back({a+b,(i+1)});
		bx.insert(a);
		by.insert(b);
	}
	for(int i=0;i<q;i++) {
		ll a,b,c;
		cin >> a >> b >> c;
		c = max(c,a+b);
		bx.insert(a);
		by.insert(b);
		qu.push_back({a,b});
		qp.push_back({c,-(i+1)});
	}
	for(auto& it: bx) {
		ll sz = mx.size();
		mx[it] = sz;
	}
	for(auto& it: by) {
		ll sz = my.size();
		my[it] = sz;
	}
	sort(qp.begin(),qp.end());
	ST sx(mx.size()),sy(my.size());
	vector<ll> res(q,0);
	for(int point = qp.size()-1;point >= 0;point--) {
		ll idx = qp[point].second;
		ll id = abs(idx)-1;
		if(idx < 0) {
			ll xv = mx[qu[id].first];
			ll yv = my[qu[id].second];
			ll vx = sx.get(xv,sx.size());
			ll vy = sy.get(0,yv);
			res[id] = vx-vy;
		} else {
			ll xv = mx[w[id].first];
			ll yv = my[w[id].second];
			sx.up(xv,1);
			sy.up(yv,1);
		}
	}
	for(int i=0;i<q;i++) {
		cout << res[i] << '\n';
	}
}

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