oj.uz

Submission #926277

# Submission time Handle Problem Language Result Execution time Memory
926277 2024-02-12T18:14:19 Z OAleksa Examination (JOI19_examination) C++14
20 / 100
 150 ms 5964 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 1e5 + 69;
int n, q, a[N], b[N], f[N], ans[N], c[N];
void Modify(int v, int val) {
	for (int i = v;i < N;i += (i & -i))
		f[i] += val;
}
int Get(int v) {
	int res = 0;
	for (int i = v;i > 0;i -= (i & -i))
		res += f[i];
	return res;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> q;
  	for (int i = 1;i <= n;i++) {
  		cin >> a[i] >> b[i];
  		c[i] = a[i] + b[i];
  	}
  	vector<tuple<int, int, int>> t1, t2, t3;
  	for (int i = 1;i <= q;i++) {
  		int x, y, z;
  		cin >> x >> y >> z;
  		if (x + y >= z) 
  			t1.push_back({x, y, i});
  		else {
  			t2.push_back({x, z, i});
  			t3.push_back({z, y, i});
  		}
  	}
  	
  	//x-y
  	//x-z
  	//z-y
  	vector<int> all;
  	for (int i = 1;i <= n;i++)
  		all.push_back(b[i]);
  	for (auto u : t1)
  		all.push_back(get<1>(u));
  	sort(all.begin(), all.end());
  	all.erase(unique(all.begin(), all.end()), all.end());
  	sort(t1.rbegin(), t1.rend());
  	vector<int> ord(n);
  	iota(ord.begin(), ord.end(), 1);
  	sort(ord.begin(), ord.end(), [&](int i, int j) {
  		return a[i] < a[j];
  	});
  	int ptr = n - 1;
  	for (auto u : t1) {
  		int x, y, ind;
  		tie(x, y, ind) = u;
  		while (ptr >= 0 && a[ord[ptr]] >= x) {
  			auto u = lower_bound(all.begin(), all.end(), b[ord[ptr]]) - all.begin() + 1;
  			Modify(u, 1);
  			ptr--;
  		}
  		int p = lower_bound(all.begin(), all.end(), y) - all.begin() + 1;
  		ans[ind] = Get(N - 1) - Get(p - 1);
  	}
  	
  	for (int i = 0;i < N;i++)
  		f[i] = 0;
  	all.clear();
  	for (int i = 1;i <= n;i++)
  		all.push_back(c[i]);
  	for (auto u : t2)
  		all.push_back(get<1>(u));
  	sort(all.begin(), all.end());
  	all.erase(unique(all.begin(), all.end()), all.end());
  	sort(t2.rbegin(), t2.rend());
  	ptr = n - 1;
  	for (auto u : t2) {
  		int x, z, ind;
  		tie(x, z, ind) = u;
  		while (ptr >= 0 && a[ord[ptr]] >= x) {
  			auto u = lower_bound(all.begin(), all.end(), c[ord[ptr]]) - all.begin() + 1;
  			Modify(u, 1);
  			ptr--;
  		}
  		int p = lower_bound(all.begin(), all.end(), z) - all.begin() + 1;
  		ans[ind] += Get(N - 1) - Get(p - 1);
  	}
  	
  	for (int i = 0;i < N;i++)
  		f[i] = 0;
  	all.clear();
  	for (int i = 1;i <= n;i++)
  		all.push_back(b[i]);
  	for (auto u : t3)
  		all.push_back(get<1>(u));
  	sort(all.begin(), all.end());
  	all.erase(unique(all.begin(), all.end()), all.end());
  	sort(t3.rbegin(), t3.rend());
  	sort(ord.begin(), ord.end(), [&](int i, int j) {
  		return c[i] < c[j];
  	});
  	ptr = n - 1;
  	for (auto u : t3) {
  		int y, z, ind;
  		tie(z, y, ind) = u;
  		while (ptr >= 0 && c[ord[ptr]] >= z) {
  			auto u = lower_bound(all.begin(), all.end(), b[ord[ptr]]) - all.begin() + 1;
  			Modify(u, 1);
  			ptr--;
  		}
  		int p = lower_bound(all.begin(), all.end(), y) - all.begin() + 1;
			ans[ind] -= Get(p);
  	}
  	for (int i = 1;i <= q;i++)
  		cout << ans[i] << '\n';
  }
  return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 856 KB Output is correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 5952 KB Output is correct
2 Correct 109 ms 5832 KB Output is correct
3 Correct 112 ms 5888 KB Output is correct
4 Correct 71 ms 5908 KB Output is correct
5 Correct 96 ms 5872 KB Output is correct
6 Correct 59 ms 5832 KB Output is correct
7 Correct 108 ms 5844 KB Output is correct
8 Correct 121 ms 5964 KB Output is correct
9 Correct 107 ms 5828 KB Output is correct
10 Correct 92 ms 5660 KB Output is correct
11 Correct 81 ms 5688 KB Output is correct
12 Correct 48 ms 5572 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 5952 KB Output is correct
2 Correct 109 ms 5832 KB Output is correct
3 Correct 112 ms 5888 KB Output is correct
4 Correct 71 ms 5908 KB Output is correct
5 Correct 96 ms 5872 KB Output is correct
6 Correct 59 ms 5832 KB Output is correct
7 Correct 108 ms 5844 KB Output is correct
8 Correct 121 ms 5964 KB Output is correct
9 Correct 107 ms 5828 KB Output is correct
10 Correct 92 ms 5660 KB Output is correct
11 Correct 81 ms 5688 KB Output is correct
12 Correct 48 ms 5572 KB Output is correct
13 Incorrect 150 ms 5800 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 0 ms 856 KB Output is correct
3 Correct 0 ms 856 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 856 KB Output is correct
10 Incorrect 3 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -