oj.uz

Submission #810807

# Submission time Handle Problem Language Result Execution time Memory
810807 2023-08-06T15:40:14 Z OrazB Examination (JOI19_examination) C++14
20 / 100
 545 ms 53628 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];
int f[N][2];
vector<int> E[N];


void add(int x, int y){
	for (int i = x; i <= M; i += i&(-i)){
		f[i][0]++;
		E[i].pb(y);
	}
	for (int i = y; i <= M; i += i&(-i)){
		f[i][1]++;
	}
}
int count(int x, int y){
	int cnt = 0;
	for (int i = x; i > 0; i -= i&(-i)){
		cnt += f[i][0];
		int l = 0, r = E[i].size()-1, pos = -1;
		while(l <= r){
			int md = (l+r)>>1;
			if (E[i][md] > y) r = md - 1;
			else{
				pos = md;
				l = md + 1;
			}
		}
		cnt -= pos+1;
	}
	for (int i = y; i > 0; i -= i&(-i)){
		cnt += f[i][1];
	}
	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 11 ms 23780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 53612 KB Output is correct
2 Correct 483 ms 53600 KB Output is correct
3 Correct 449 ms 53628 KB Output is correct
4 Correct 259 ms 43688 KB Output is correct
5 Correct 291 ms 45836 KB Output is correct
6 Correct 64 ms 27476 KB Output is correct
7 Correct 395 ms 51176 KB Output is correct
8 Correct 383 ms 50860 KB Output is correct
9 Correct 326 ms 48092 KB Output is correct
10 Correct 287 ms 46128 KB Output is correct
11 Correct 234 ms 43488 KB Output is correct
12 Correct 48 ms 27288 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 53612 KB Output is correct
2 Correct 483 ms 53600 KB Output is correct
3 Correct 449 ms 53628 KB Output is correct
4 Correct 259 ms 43688 KB Output is correct
5 Correct 291 ms 45836 KB Output is correct
6 Correct 64 ms 27476 KB Output is correct
7 Correct 395 ms 51176 KB Output is correct
8 Correct 383 ms 50860 KB Output is correct
9 Correct 326 ms 48092 KB Output is correct
10 Correct 287 ms 46128 KB Output is correct
11 Correct 234 ms 43488 KB Output is correct
12 Correct 48 ms 27288 KB Output is correct
13 Incorrect 545 ms 53564 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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