oj.uz

답안 #699055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699055 2023-02-15T13:15:42 Z Sandarach151 Examination (JOI19_examination) C++17
0 / 100
 190 ms 11080 KB 
#include <bits/stdc++.h>
using namespace std;
 
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(n);
	segmenttree two(n);
	vector<pair<int, int> > arr11(n);
	vector<pair<int, int> > arr12(n);
	vector<pair<int, int> > arr21(n);
	vector<pair<int, int> > arr22(n);
	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(i, 1);
		two.update(i, 1);
	}
	sort(arr, arr+n);
	for(int i=0; i<n; i++){
		arr11[i].first = arr[i].second.first;
		arr21[i].first = arr[i].second.second;
		
		arr12[i].first = arr[i].second.first;
		arr12[i].second = i;
		arr22[i].first = arr[i].second.second;
		arr22[i].second = i;
	}
	sort(arr12.begin(), arr12.end());
	sort(arr22.begin(), arr22.end());
	for(int i=0; i<n; i++){
		arr11[arr12[i].second].second=i;
		arr21[arr22[i].second].second=i;
	}
	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 aa = get<1>(queries[posq].first);
			int bb = get<2>(queries[posq].first);
			pair<int, int> temp1 = {aa, 0};
			pair<int, int> temp2 = {bb, 0};
			int a = lower_bound(arr12.begin(), arr12.end(), temp1)-arr12.begin();
			int b = lower_bound(arr22.begin(), arr22.end(), temp2)-arr22.begin();
			int c = one.query(min(a, n-1), n-1);
			int d = two.query(min(b, n-1), n-1);
			int e = n-i;
			queries[posq].second = c+d-e;
			posq++;
		}
		one.update(arr11[i].second, -1);
		two.update(arr21[i].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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Incorrect 1 ms 224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 10996 KB Output is correct
2 Incorrect 174 ms 11080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 10996 KB Output is correct
2 Incorrect 174 ms 11080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Incorrect 1 ms 224 KB Output isn't correct
7 Halted 0 ms 0 KB -