Submission #404727

#	Time	Username	Problem	Language	Result	Execution time	Memory
404727		usuyus	Examination (JOI19_examination)	C++14	100 / 100	949 ms	311632 KiB

examination

#include <bits/stdc++.h>
#define N 200005
#define M 1000000007
using namespace std;
using ll = long long;

struct ImplicitSegTree {
	struct Node {
		ll val;
		Node *lft, *rgt;;

		Node() : val(0), lft(nullptr), rgt(nullptr) {}

		void push() {
			if (!lft) lft = new Node();
			if (!rgt) rgt = new Node();
		}

		void update(ll l, ll r, ll idx) {
			++val;
			if (l == r) return;
			push();

			ll m = (l+r) / 2;
			if (idx <= m) lft->update(l, m, idx);
			else rgt->update(m+1, r, idx);
		}

		ll query(ll l, ll r, ll lq, ll rq) {
			if (r < lq || rq < l) return 0;
			if (lq <= l && r <= rq) return val;
			push();

			ll m = (l+r) / 2;
			return (
				lft->query(l, m, lq, rq) +
				rgt->query(m+1, r, lq, rq)
			);
		}
	};

	ll n;
	vector<Node> nodes;

	ImplicitSegTree(ll n) : n(n), nodes() {
		nodes.emplace_back();
	}

	void update(ll idx) {
		nodes[0].update(0, n, idx);
	}

	ll query(ll l, ll r) {
		return nodes[0].query(0, n, l, r);
	}
};

struct Query {
	ll a, b, c, idx;

	bool operator<(Query rhs) const {
		if (c == rhs.c) return idx < rhs.idx;
		else return c > rhs.c;
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	ll n, q; cin>>n>>q;
	vector<Query> qs;

	for (int i=0; i<n; i++) {
		int x, y; cin>>x>>y;
		qs.push_back({x, y, x+y, -1});
	}

	for (int i=0; i<q; i++) {
		int a, b, c; cin>>a>>b>>c;
		c = max(c, a+b);
		qs.push_back({a, b, c, i});
	}

	sort(qs.begin(), qs.end());
	
	ImplicitSegTree sega(M), segb(M);
	vector<ll> ans(q);
	ll cnt = 0;

	for (auto [a, b, c, idx] : qs) {
		if (idx == -1) { // point
			sega.update(a);
			segb.update(b);
			++cnt;
		} else { // query
			ll aq = sega.query(0, a-1);
			ll bq = segb.query(0, b-1);
			ans[idx] = cnt - aq - bq;
		}
	}

	for (ll x : ans) cout<<x<<endl;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:90:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |  for (auto [a, b, c, idx] : qs) {
      |            ^

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