oj.uz

Submission #119106

# Submission time Handle Problem Language Result Execution time Memory
119106 2019-06-20T10:48:02 Z raghav0307 Examination (JOI19_examination) C++14
41 / 100
 116 ms 12264 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 = 2e5 + 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;
	for(int i = 0; i < n; i++){
		int temp1, temp2;
		cin >> temp1 >> temp2;
		// cin >> score[i].ff >> score[i].ss;
		score.pb({temp1, 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];
	}
	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});
			// cout << rule[i][0] << " " << rule[i][1] << " " << rule[i][2] << "\n"; 
		}
	}
	sort(criter2.begin(), criter2.end());
	sort(score.begin(), score.end(), custom);

	// for(int i = 0; i < n; i++)
	// 	cout << score[i].ff << " " << score[i].ss << "\n";
	// for(auto x : criter2)
	// 	cout << x.ff << " " << x.ss << "\n";

	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 Correct 3 ms 1920 KB Output is correct
2 Correct 3 ms 2048 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Runtime error 6 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9492 KB Output is correct
2 Correct 92 ms 9444 KB Output is correct
3 Correct 95 ms 9592 KB Output is correct
4 Correct 80 ms 9316 KB Output is correct
5 Correct 81 ms 9316 KB Output is correct
6 Correct 72 ms 9416 KB Output is correct
7 Correct 90 ms 9956 KB Output is correct
8 Correct 94 ms 9876 KB Output is correct
9 Correct 89 ms 9724 KB Output is correct
10 Correct 78 ms 9316 KB Output is correct
11 Correct 82 ms 9416 KB Output is correct
12 Correct 68 ms 9220 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9492 KB Output is correct
2 Correct 92 ms 9444 KB Output is correct
3 Correct 95 ms 9592 KB Output is correct
4 Correct 80 ms 9316 KB Output is correct
5 Correct 81 ms 9316 KB Output is correct
6 Correct 72 ms 9416 KB Output is correct
7 Correct 90 ms 9956 KB Output is correct
8 Correct 94 ms 9876 KB Output is correct
9 Correct 89 ms 9724 KB Output is correct
10 Correct 78 ms 9316 KB Output is correct
11 Correct 82 ms 9416 KB Output is correct
12 Correct 68 ms 9220 KB Output is correct
13 Correct 112 ms 10344 KB Output is correct
14 Correct 107 ms 11744 KB Output is correct
15 Correct 95 ms 11332 KB Output is correct
16 Correct 99 ms 11596 KB Output is correct
17 Correct 96 ms 11556 KB Output is correct
18 Correct 79 ms 9956 KB Output is correct
19 Correct 116 ms 12084 KB Output is correct
20 Correct 108 ms 12264 KB Output is correct
21 Correct 113 ms 11448 KB Output is correct
22 Correct 82 ms 10468 KB Output is correct
23 Correct 96 ms 10464 KB Output is correct
24 Correct 66 ms 9576 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 3 ms 2048 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Runtime error 6 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -