Submission #119111

#	Time	Username	Problem	Language	Result	Execution time	Memory
119111		raghav0307	Examination (JOI19_examination)	C++14	20 / 100	470 ms	24632 KiB

examination

/*raghav0307 - Raghav Gupta*/

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll
const int MAXN = 5e5 + 5;

bool custom(pair<int, int> a, pair<int, int> b){
	if(a == b)
		return false;
	if(a.ff + a.ss > b.ff + b.ss)
		return false;
	if(a.ff + a.ss < b.ff + b.ss)
		return true;
	if(a.ff > b.ff)
		return false;
	return true;
}

int bit[MAXN], ans[MAXN], rule[MAXN][3];
vector<pair<int, int> > score;

void add(int pos, int delta){
	for( ; pos < MAXN; pos = pos | ( pos + 1))
		bit[pos] += delta;
}

int sum(int pos){
	int ans = 0;
	for( ; pos >= 0; pos = (pos & (pos+1)) - 1)
		ans += bit[pos];
	return ans;
}

int sum(int l, int r){
	if(l > r)	return 0;
	return sum(r) - sum(l-1);
}

signed main(){
	fast_io();
	int n, q;
	cin >> n >> q;
	vector<int> coordinate;
	for(int i = 0; i < n; i++){
		int temp1, temp2;
		cin >> temp1 >> temp2;
		// cin >> score[i].ff >> score[i].ss;
		score.pb({temp1, temp2});
		coordinate.pb(temp1); coordinate.pb(temp2);
	}
	sort(score.begin(), score.end());
	vector<pair<pii, int> > criter;
	for(int i = 0; i < q; i++){
		cin >> rule[i][0] >> rule[i][1] >> rule[i][2];
		coordinate.pb(rule[i][0]);
		coordinate.pb(rule[i][1]);
		coordinate.pb(rule[i][2]);
	}
	sort(coordinate.begin(), coordinate.end());
	map<int, int> mp;
	mp[coordinate[0]] = 0;
	int pos = 1;
	for(int i = 1; i < (int)coordinate.size(); i++){
		if(coordinate[i] == coordinate[i-1]) continue;
		mp[coordinate[i]] = pos;
		pos++;
	}

	for(auto &x : score){
		x.ff = mp[x.ff];
		x.ss = mp[x.ss];
	}
	for(int i = 0; i < q; i++){
		for(int j = 0; j < 3; j++){
			rule[i][j] = mp[rule[i][j]];
		}
	}

	for(int i = 0; i < q; i++){
		if(rule[i][0] + rule[i][1] >= rule[i][2]){
			criter.pb({{rule[i][0], rule[i][1]}, i});
		}
	}
	sort(criter.begin(), criter.end());
	int at = n-1;
	memset(bit, 0, sizeof(bit));
	while(!criter.empty()){
		auto x = criter.back(); criter.pop_back();
		while(at >= 0 and score[at].ff >= x.ff.ff){
			add(score[at].ss, 1);
			at--;
		}
		ans[x.ss] = sum(x.ff.ss, MAXN-1);
	}

	vector<pii> criter2;
	for(int i = 0; i < q; i++){
		if(rule[i][0] + rule[i][1] < rule[i][2]){
			criter2.pb({rule[i][2], i});
		}
	}
	sort(criter2.begin(), criter2.end());
	sort(score.begin(), score.end(), custom);

	memset(bit, 0, sizeof(bit));
	at = n-1;
	for(int i = (int)criter2.size() - 1; i >= 0; i--){
		while(at >= 0 and score[at].ff + score[at].ss >= criter2[i].ff){
			add(score[at].ff, 1);
			at--;
		}
		ans[criter2[i].ss] += n - at - 1;
		ans[criter2[i].ss] -= sum(0, rule[criter2[i].ss][0] - 1);
	}

	memset(bit, 0, sizeof(bit));
	at = n-1;
	for(int i = (int)criter2.size() - 1; i >= 0; i--){
		while(at >= 0 and score[at].ff + score[at].ss >= criter2[i].ff){
			add(score[at].ss, 1);
			at--;
		}
		ans[criter2[i].ss] -= sum(0, rule[criter2[i].ss][1] - 1);
	}

	for(int i = 0; i < q; i++)
		cout << ans[i] << "\n";
	return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57