oj.uz

Submission #379923

# Submission time Handle Problem Language Result Execution time Memory
379923 2021-03-19T17:28:47 Z voldemort Examination (JOI19_examination) C++17
0 / 100
 815 ms 15544 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 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 20 ms 1260 KB Output is correct
8 Correct 20 ms 1280 KB Output is correct
9 Correct 20 ms 1260 KB Output is correct
10 Correct 17 ms 1004 KB Output is correct
11 Correct 19 ms 1260 KB Output is correct
12 Incorrect 13 ms 620 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 15544 KB Output is correct
2 Correct 790 ms 15460 KB Output is correct
3 Correct 815 ms 15516 KB Output is correct
4 Correct 671 ms 11360 KB Output is correct
5 Correct 667 ms 13024 KB Output is correct
6 Incorrect 452 ms 7652 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 810 ms 15544 KB Output is correct
2 Correct 790 ms 15460 KB Output is correct
3 Correct 815 ms 15516 KB Output is correct
4 Correct 671 ms 11360 KB Output is correct
5 Correct 667 ms 13024 KB Output is correct
6 Incorrect 452 ms 7652 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 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 20 ms 1260 KB Output is correct
8 Correct 20 ms 1280 KB Output is correct
9 Correct 20 ms 1260 KB Output is correct
10 Correct 17 ms 1004 KB Output is correct
11 Correct 19 ms 1260 KB Output is correct
12 Incorrect 13 ms 620 KB Output isn't correct
13 Halted 0 ms 0 KB -