oj.uz

Submission #119111

# Submission time Handle Problem Language Result Execution time Memory
119111 2019-06-20T11:22:19 Z raghav0307 Examination (JOI19_examination) C++14
20 / 100
 470 ms 24632 KB 
/*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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 23316 KB Output is correct
2 Correct 440 ms 23340 KB Output is correct
3 Correct 356 ms 23380 KB Output is correct
4 Correct 255 ms 22616 KB Output is correct
5 Correct 258 ms 22608 KB Output is correct
6 Correct 103 ms 17236 KB Output is correct
7 Correct 350 ms 23328 KB Output is correct
8 Correct 339 ms 23328 KB Output is correct
9 Correct 292 ms 22732 KB Output is correct
10 Correct 230 ms 22484 KB Output is correct
11 Correct 232 ms 22480 KB Output is correct
12 Correct 87 ms 16852 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 23316 KB Output is correct
2 Correct 440 ms 23340 KB Output is correct
3 Correct 356 ms 23380 KB Output is correct
4 Correct 255 ms 22616 KB Output is correct
5 Correct 258 ms 22608 KB Output is correct
6 Correct 103 ms 17236 KB Output is correct
7 Correct 350 ms 23328 KB Output is correct
8 Correct 339 ms 23328 KB Output is correct
9 Correct 292 ms 22732 KB Output is correct
10 Correct 230 ms 22484 KB Output is correct
11 Correct 232 ms 22480 KB Output is correct
12 Correct 87 ms 16852 KB Output is correct
13 Incorrect 470 ms 24632 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4224 KB Output isn't correct
2 Halted 0 ms 0 KB -