Submission #698964

#	Time	Username	Problem	Language	Result	Execution time	Memory
698964		Sandarach151	Examination (JOI19_examination)	C++17	0 / 100	3072 ms	13108 KiB

examination

#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(); 
			//cout << a << ' ' << b << "\n\n\n\n";
			int c = one.query(a, n-1);
			int d = two.query(b, 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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57