oj.uz

Submission #810906

# Submission time Handle Problem Language Result Execution time Memory
810906 2023-08-06T17:19:44 Z OrazB Examination (JOI19_examination) C++14
0 / 100
 3000 ms 269992 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define pii pair <int, int>
// #define ordered_set tree<pair<pii,int>, null_type,less<pair<pii,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pb push_back
#define ff first
#define ss second
 
const int N = 1e6;
int M = 0;
int n, q;
map<int,int> mp, now1, now2;
int pos[N], s[N], t[N], ans[N];
int x[N], y[N], z[N], ind[N];
map<pii,int> f;
vector<int> E[N];
 
 
void add(int x, int y){
	for (int i = x; i <= M; i += i&(-i)){
		f[{i,-1}]++;
	}
	for (int i = y; i <= M; i += i&(-i)){
		f[{i, -2}]++;
	}
	for (int i = x; i <= M; i += i&(-i)){
		for (int j = y; j <= M; j += j&(-j)){
			f[{i, j}]++;
		}
	}

}
int count(int x, int y){
	int cnt = 0;
	for (int i = x; i > 0; i -= i&(-i)){
		cnt += f[{i,-1}];
		for (int j = y; j > 0; j -= j&(-j)){
			cnt -= f[{i, j}];
		}
	}
	for (int i = y; i > 0; i -= i&(-i)){
		cnt += f[{i,-2}];
	}
	return cnt;
}
 
int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	set<int> dec1, dec2;
	for (int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
		dec1.insert(s[i]);
		dec2.insert(t[i]);
	}
	for (int i = 1; i <= q; i++){
		cin >> x[i] >> y[i] >> z[i];
		dec1.insert(x[i]);
		dec2.insert(y[i]);
	}
	int T = 0;
	for (auto i : dec1){
		if (!mp[i]++) now1[i] = ++T;
	}
	M = T;
	T = 0;
	mp.clear();
	for (auto i : dec2){
		if (!mp[i]++) now2[i] = ++T;
	}
	M = max(M, T);
	for (int i = 1; i <= n; i++){
		add(now1[s[i]], now2[t[i]]);
	}
	for (int i = 1; i <= M; i++) sort(all(E[i]));
	for (int i = 1; i <= q; i++){
		cout << n-count(now1[x[i]]-1, now2[y[i]]-1) << '\n';
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 269992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 269992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23860 KB Output isn't correct
2 Halted 0 ms 0 KB -