oj.uz

Submission #379924

# Submission time Handle Problem Language Result Execution time Memory
379924 2021-03-19T17:29:03 Z voldemort Examination (JOI19_examination) C++17
0 / 100
 590 ms 13052 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
	private: vector<int> tree; int n;
	int LSOne(int x) {
		return x&(-x);
	}

	public:
		void build(int x) {
			n = x;
			tree.resize(n+1);
		}
		int sum(int a) {
			int sum = 0;
			for (; a > 0; a -= LSOne(a)) sum += tree[a];
			return sum;
		}
		int sum(int a, int b) {
			return sum(b) - (a == 1 ? 0 : sum(a-1));
		}
		void update(int p, int v) {
			for (; p < n+1; p += LSOne(p)) tree[p] += v;
		}
};

int n, q, pt = 1;
vector<array<int, 4>> pts; // {s1, s2, sum, index: -1 -> contestant, else query index}
vi ans;
BIT tree;
map<int, int> mp;

void solve(int l, int r) {
	if (l == r) return;
	
	int mid = (l+r)/2;
	
	vector<array<int, 3>> curr; // {s2, sum, index: 1 -> contestant, else -ve query index}
	for_(i, mid+1, r+1) if (pts[i][3] != -1) curr.push_back({pts[i][1], pts[i][2], -pts[i][3]});
	for_(i, l, mid+1) if (pts[i][3] == -1) curr.push_back({pts[i][1], pts[i][2], 1});
	
	sort(curr.rbegin(), curr.rend());
	
	for (auto &i: curr) {
		if (i[2] == 1) tree.update(i[1], 1);
		else ans[-i[2]] += tree.sum(i[1], pt);
	}
	
	for (auto &i: curr) if (i[2] == 1) tree.update(i[1], -1);
	
	solve(l, mid); solve(mid+1, r);
}



int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	pts.resize(n+q); ans.resize(q);
	
	for_(i, 0, n) {
		cin >> pts[i][0] >> pts[i][1];
		pts[i][2] = pts[i][0]+pts[i][1]; pts[i][3] = -1;
		mp[pts[i][1]] = mp[pts[i][2]] = 0;
	}
	for_(i, n, n+q) {
		cin >> pts[i][0] >> pts[i][1] >> pts[i][2];
		pts[i][3] = i-n;
		mp[pts[i][1]] = mp[pts[i][2]] = 0;
	}
	
	for (auto &i: mp) mp[i.first] = pt++;
	for_(i, 0, n+q) {
		pts[i][1] = mp[pts[i][1]]; pts[i][2] = mp[pts[i][2]]; 
	}
	
	sort(pts.rbegin(), pts.rend());
	tree.build(pt);
	solve(0, n+q-1);
	
	for (auto i: ans) cout << i << endl;
	cout << endl;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 17 ms 1132 KB Output is correct
8 Correct 14 ms 1132 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 11 ms 876 KB Output is correct
11 Correct 13 ms 1132 KB Output is correct
12 Incorrect 6 ms 492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 13052 KB Output is correct
2 Correct 590 ms 12924 KB Output is correct
3 Correct 563 ms 12900 KB Output is correct
4 Correct 439 ms 9568 KB Output is correct
5 Correct 452 ms 11232 KB Output is correct
6 Incorrect 236 ms 6756 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 13052 KB Output is correct
2 Correct 590 ms 12924 KB Output is correct
3 Correct 563 ms 12900 KB Output is correct
4 Correct 439 ms 9568 KB Output is correct
5 Correct 452 ms 11232 KB Output is correct
6 Incorrect 236 ms 6756 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 17 ms 1132 KB Output is correct
8 Correct 14 ms 1132 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 11 ms 876 KB Output is correct
11 Correct 13 ms 1132 KB Output is correct
12 Incorrect 6 ms 492 KB Output isn't correct
13 Halted 0 ms 0 KB -