Submission #1080078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080078		BuzzyBeez	Examination (JOI19_examination)	C++17	100 / 100	408 ms	12120 KiB

examination

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

vector<int> tbc;

void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(int key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}

struct point {
	int Ox, Oy, Oz; char op; int id;
	
	point() {}
	
	friend istream& operator >> (istream& in, point& o) {
		in >> o.Ox >> o.Oy >> o.Oz;
		tbc.push_back(o.Oz); o.op = '?';
		return in;
	}
	
	friend ostream& operator << (ostream& out, const point& o) {
		out << o.op << ' ' << o.Ox << ' ' << o.Oy << ' ' << o.Oz;
		return out;
	}
} S[N + 8];
int ans[100008];

bool by_Ox(point& a, point& b) {
	if (a.Ox == b.Ox) return a.op < b.op;
	return a.Ox > b.Ox;
}
bool by_Oy(point& a, point& b) {return a.Oy > b.Oy;}

struct Binary_Indexed_Tree {
	int BIT[N + 8];
	
	Binary_Indexed_Tree() {memset(BIT, 0, sizeof BIT);}
	
	int pt, res;
	
	void update(int u, int v) {
	    pt = u;
	    while (pt <= N) {
	    	BIT[pt] += v;
	        pt += pt & -pt;
	    }
	}
	
	int pf(int p) {
		if (p <= 0) return 0;
	    pt = p; res = 0;
	    while (pt) {
	        res += BIT[pt];
	        pt -= pt & -pt;
	    }
	    return res;
	}
	
	int range(int l, int r) {
		if (l > r) return 0;
		return pf(r) - pf(l - 1);
	}
	
	int query(int i) {return range(i, N);}
} tree;

void dnc(int l, int r) {
	if (l >= r) return;
	int mid = (l + r) / 2, pt1, pt2 = l - 1;
	dnc(l, mid); dnc(mid + 1, r);
	vector<int> del;
	for (pt1 = mid + 1; pt1 <= r; ++pt1) if (S[pt1].op == '?') {
		while (pt2 < mid && S[pt2 + 1].Oy >= S[pt1].Oy) {
			++pt2;
			if (S[pt2].op == '+') tree.update(S[pt2].Oz, +1), del.push_back(S[pt2].Oz);
		}
		ans[S[pt1].id] += tree.query(S[pt1].Oz);
	}
	for (int i : del) tree.update(i, -1);
	del.clear();
	sort(S + l, S + r + 1, by_Oy);
	// cout << l << ' ' << r << '\n';
	// for (int i = l; i <= r; ++i) cout << S[i] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> S[i].Ox >> S[i].Oy; S[i].Oz = S[i].Ox + S[i].Oy;
		S[i].op = '+'; tbc.push_back(S[i].Oz);
	}
	for (int i = 1; i <= q; ++i) cin >> S[n + i], S[n + i].id = i;
	compress(); sort(S + 1, S + n + q + 1, by_Ox);
	for (int i = 1; i <= n + q; ++i) S[i].Oz = order(S[i].Oz);
	dnc(1, n + q);
	for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

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