Submission #926281

#	Time	Username	Problem	Language	Result	Execution time	Memory
926281		OAleksa	Examination (JOI19_examination)	C++14	22 / 100	164 ms	15140 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
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 - 1);
  	}
  	for (int i = 1;i <= q;i++)
  		cout << ans[i] << '\n';
  }
  return 0;
}

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