Submission #698956

#	Time	Username	Problem	Language	Result	Execution time	Memory
698956		Sandarach151	Examination (JOI19_examination)	C++17	41 / 100	3089 ms	10508 KiB

examination

#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
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 0 / 57