oj.uz

Submission #698956

# Submission time Handle Problem Language Result Execution time Memory
698956 2023-02-15T02:39:23 Z Sandarach151 Examination (JOI19_examination) C++17
41 / 100
 3000 ms 10508 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXX = 100005;

class segmenttree{
	private:
		vector<int> vect;
		int sze;		
		void privupdate(int segpos, int segleft, int segright, int arrpos, int val){
			if(segleft!=segright){
				int segmid = (segleft+segright)/2;
				if(arrpos<=segmid){
					privupdate(2*segpos+1, segleft, segmid, arrpos, val);
				}
				else{
					privupdate(2*segpos+2, segmid+1, segright, arrpos, val);
				}
				vect[segpos]=vect[2*segpos+1]+vect[2*segpos+2];
			}
			else{
				vect[segpos]+=val;
			}
		}
		int privquery(int segpos, int segleft, int segright, int arrleft, int arrright){
			if(arrleft==segleft && arrright==segright){
				return vect[segpos];
			}
			else{
				int segmid = (segleft+segright)/2;
				if(arrright<=segmid){
					return privquery(2*segpos+1, segleft, segmid, arrleft, arrright);
				}
				else if(arrleft>segmid){
					return privquery(2*segpos+2, segmid+1, segright, arrleft, arrright);
				}
				else{
					return privquery(2*segpos+1, segleft, segmid, arrleft, segmid)+privquery(2*segpos+2, segmid+1, segright, segmid+1, arrright);
				}
			}
		}
	public:
		segmenttree(int _sze):sze(_sze){
			vect.resize(4*sze+5, 0);
		}
		int query(int left, int right){
			return privquery(0, 0, sze-1, left, right);
		}
		void update(int pos, int val){
			privupdate(0, 0, sze-1, pos, val);
		}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q;
	cin >> n >> q;
	pair<int, pair<int, int> > arr[n];
	segmenttree one(MAXX);
	segmenttree two(MAXX);
	for(int i=0; i<n; i++){
		cin >> arr[i].second.first >> arr[i].second.second;
		arr[i].first = arr[i].second.first+arr[i].second.second;
		one.update(arr[i].second.first, 1);
		two.update(arr[i].second.second, 1);
	}
	sort(arr, arr+n);
	pair<tuple<int, int, int, int>, int> queries[q]; // sum, first, second, pos, ans;
	for(int i=0; i<q; i++){
		int a, b, c;
		cin >> a >> b >> c;
		queries[i].first = {max(c, a+b), a, b, i};
	}
	sort(queries, queries+q);
	int posq = 0;
	for(int i=0; i<n; i++){
		while(posq<q && get<0>(queries[posq].first)<=arr[i].first){
			int a = get<1>(queries[posq].first);
			int b = get<2>(queries[posq].first);
			//cout << a << ' ' << b << "\n\n\n\n";
			int c = one.query(a, MAXX-1);
			int d = two.query(b, MAXX-1);
			int e = n-i;
			queries[posq].second = c+d-e;
			posq++;
		}
		one.update(arr[i].second.first, -1);
		two.update(arr[i].second.second, -1);
	}
	int ans[q];
	for(int i=0; i<q; i++){
		ans[get<3>(queries[i].first)]=queries[i].second;
	}
	for(int i=0; i<q; i++){
		cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Execution timed out 3089 ms 3412 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9988 KB Output is correct
2 Correct 140 ms 9980 KB Output is correct
3 Correct 141 ms 9932 KB Output is correct
4 Correct 107 ms 9312 KB Output is correct
5 Correct 106 ms 9220 KB Output is correct
6 Correct 88 ms 8444 KB Output is correct
7 Correct 136 ms 9932 KB Output is correct
8 Correct 138 ms 9860 KB Output is correct
9 Correct 131 ms 9820 KB Output is correct
10 Correct 104 ms 8996 KB Output is correct
11 Correct 98 ms 9088 KB Output is correct
12 Correct 68 ms 8192 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9988 KB Output is correct
2 Correct 140 ms 9980 KB Output is correct
3 Correct 141 ms 9932 KB Output is correct
4 Correct 107 ms 9312 KB Output is correct
5 Correct 106 ms 9220 KB Output is correct
6 Correct 88 ms 8444 KB Output is correct
7 Correct 136 ms 9932 KB Output is correct
8 Correct 138 ms 9860 KB Output is correct
9 Correct 131 ms 9820 KB Output is correct
10 Correct 104 ms 8996 KB Output is correct
11 Correct 98 ms 9088 KB Output is correct
12 Correct 68 ms 8192 KB Output is correct
13 Correct 141 ms 10424 KB Output is correct
14 Correct 143 ms 10388 KB Output is correct
15 Correct 144 ms 9984 KB Output is correct
16 Correct 110 ms 9548 KB Output is correct
17 Correct 111 ms 9620 KB Output is correct
18 Correct 90 ms 8608 KB Output is correct
19 Correct 142 ms 10416 KB Output is correct
20 Correct 140 ms 10444 KB Output is correct
21 Correct 142 ms 10508 KB Output is correct
22 Correct 100 ms 9036 KB Output is correct
23 Correct 98 ms 9080 KB Output is correct
24 Correct 67 ms 8104 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Execution timed out 3089 ms 3412 KB Time limit exceeded
5 Halted 0 ms 0 KB -