oj.uz

Submission #810794

# Submission time Handle Problem Language Result Execution time Memory
810794 2023-08-06T15:23:48 Z OrazB Examination (JOI19_examination) C++14
2 / 100
 3000 ms 28684 KB 
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#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;
const int M = 1e5;
int n, q;
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;
	for (int i = 1; i <= n; i++){
		cin >> s[i] >> t[i];
		if (n > 3000 and q > 3000) add(s[i], t[i]);
		// pos[i] = i;
	}
	for (int i = 1; i <= M; i++) sort(all(E[i]));
	// sort(pos+1,pos+n+1, [&](int x, int y){
	// 	return (s[x]+t[x]) > (s[y]+t[y]); 
	// });
	for (int i = 1; i <= q; i++){
		cin >> x[i] >> y[i] >> z[i];
		int cnt = 0;
		for (int j = 1;  j <= n; j++){
			cnt += (x[i] <= s[j] and y[i] <= t[j] and z[i] <= s[j]+t[j]);
		}
		if (n > 3000 and q > 3000)	
			cout << n-count(x[i]-1, y[i]-1) << '\n';
		else 
			cout << cnt << '\n';
		// ind[i] = i;
	}
	// sort(ind+1,ind+q+1, [&](int x, int y){
	// 	return z[x] > z[y]; 
	// });
	// int l = 0;
	// for (int i = 1; i <= q; i++){
	// 	while(l < n and s[pos[l+1]]+t[pos[l+1]] >= z[ind[i]]){
	// 		l++;
	// 		add(s[pos[l]], t[pos[l]]);
	// 	}
	// 	ans[ind[i]] = l-count(x[ind[i]]-1, y[ind[i]]-1);
	// }
	// for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 16 ms 23812 KB Output is correct
4 Correct 13 ms 23788 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23804 KB Output is correct
7 Correct 51 ms 23996 KB Output is correct
8 Correct 49 ms 24020 KB Output is correct
9 Correct 50 ms 24028 KB Output is correct
10 Correct 51 ms 23932 KB Output is correct
11 Correct 51 ms 23992 KB Output is correct
12 Correct 50 ms 23924 KB Output is correct
13 Correct 50 ms 24032 KB Output is correct
14 Correct 51 ms 24020 KB Output is correct
15 Correct 51 ms 23948 KB Output is correct
16 Correct 29 ms 23932 KB Output is correct
17 Correct 39 ms 23892 KB Output is correct
18 Correct 21 ms 23892 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3093 ms 28684 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 3093 ms 28684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 16 ms 23812 KB Output is correct
4 Correct 13 ms 23788 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23804 KB Output is correct
7 Correct 51 ms 23996 KB Output is correct
8 Correct 49 ms 24020 KB Output is correct
9 Correct 50 ms 24028 KB Output is correct
10 Correct 51 ms 23932 KB Output is correct
11 Correct 51 ms 23992 KB Output is correct
12 Correct 50 ms 23924 KB Output is correct
13 Correct 50 ms 24032 KB Output is correct
14 Correct 51 ms 24020 KB Output is correct
15 Correct 51 ms 23948 KB Output is correct
16 Correct 29 ms 23932 KB Output is correct
17 Correct 39 ms 23892 KB Output is correct
18 Correct 21 ms 23892 KB Output is correct
19 Execution timed out 3093 ms 28684 KB Time limit exceeded
20 Halted 0 ms 0 KB -