oj.uz

Submission #810806

# Submission time Handle Problem Language Result Execution time Memory
810806 2023-08-06T15:39:37 Z OrazB Examination (JOI19_examination) C++14
20 / 100
 284 ms 49080 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;
int now1[N], now2[N];
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 10 ms 23768 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 270 ms 46264 KB Output is correct
2 Correct 280 ms 48744 KB Output is correct
3 Correct 263 ms 48748 KB Output is correct
4 Correct 186 ms 39672 KB Output is correct
5 Correct 216 ms 43980 KB Output is correct
6 Correct 57 ms 28576 KB Output is correct
7 Correct 229 ms 47012 KB Output is correct
8 Correct 234 ms 46916 KB Output is correct
9 Correct 201 ms 44924 KB Output is correct
10 Correct 226 ms 44196 KB Output is correct
11 Correct 143 ms 39504 KB Output is correct
12 Correct 46 ms 28352 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 46264 KB Output is correct
2 Correct 280 ms 48744 KB Output is correct
3 Correct 263 ms 48748 KB Output is correct
4 Correct 186 ms 39672 KB Output is correct
5 Correct 216 ms 43980 KB Output is correct
6 Correct 57 ms 28576 KB Output is correct
7 Correct 229 ms 47012 KB Output is correct
8 Correct 234 ms 46916 KB Output is correct
9 Correct 201 ms 44924 KB Output is correct
10 Correct 226 ms 44196 KB Output is correct
11 Correct 143 ms 39504 KB Output is correct
12 Correct 46 ms 28352 KB Output is correct
13 Incorrect 284 ms 49080 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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