oj.uz

Submission #223114

# Submission time Handle Problem Language Result Execution time Memory
223114 2020-04-14T19:29:03 Z AQT Examination (JOI19_examination) C++14
100 / 100
 2474 ms 127092 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

struct node{
	int l, r;
	tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> st;
};

int N, Q;
pair<int, int> arr[100005];
int ans[100005];
int a[100005], b[100005], c[100005];
pair<int, int> qu[100005];
node seg[400005];
vector<int> cmp;

void build(int l, int r, int idx){
	seg[idx].l = l, seg[idx].r = r;
	if(l == r){
		return;
	}
	int mid = l+r>>1;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
}

void upd(int p, int v, int idx){
	seg[idx].st.insert(v);
	if(seg[idx].l == seg[idx].r){
		return;
	}
	upd(p, v, 2*idx + (p > seg[idx].l + seg[idx].r >> 1));
}

int query(int l, int r, int k, int idx){
	if(seg[idx].l == l && seg[idx].r == r){
		/*
		try{
			return seg[idx].st.order_of_key(k-1);
		}
		catch(exception &e){
			return 0;
		}
		*/
		//cout << seg[idx].st.order_of_key(k-1) << "\n";
		return seg[idx].st.order_of_key(k-1);
	}
	int mid = seg[idx].l + seg[idx].r >> 1;
	if(r <= mid){
		return query(l, r, k, 2*idx);
	}
	else if(l > mid){
		return query(l, r, k, 2*idx+1);
	}
	else{
		return query(l, mid, k, 2*idx) + query(mid+1, r, k, 2*idx+1);
	}
}

bool comp1(pair<int, int> a, pair<int, int> b){
	return a.first+a.second > b.first+b.second;
}

int getidx(int v){
	return lower_bound(cmp.begin(), cmp.end(), v) - cmp.begin() + 1;
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for(int i= 1; i<=N; i++){
		cin >> arr[i].first >> arr[i].second;
		cmp.push_back(arr[i].first);
	}
	sort(arr+1, arr+1+N, comp1);
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	int M = cmp.size();
	for(int q = 1; q<=Q; q++){
		cin >> a[q] >> b[q] >> c[q];		
		qu[q] = {c[q], q};
	}
	build(1, M, 1);
	sort(qu+1, qu+1+N, greater<pair<int, int>>());
	int idx = 1;
	for(int q = 1; q<=Q; q++){
		while(idx <= N && arr[idx].first + arr[idx].second >= qu[q].first){
			upd(getidx(arr[idx].first), arr[idx].second, 1);
			idx++;
		}
		int n = qu[q].second;
		//cout << n << " " << getidx(a[n]) << "\n";
		if(getidx(a[n]) > M){
			continue;
		}
		ans[n] = query(getidx(a[n]), M, b[n], 1);
	}
	for(int q = 1; q<=Q; q++){
		cout << ans[q] << "\n";
	}
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:26:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r>>1;
            ~^~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:36:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  upd(p, v, 2*idx + (p > seg[idx].l + seg[idx].r >> 1));
                         ~~~~~~~~~~~^~~~~~~~~~~~
examination.cpp: In function 'int query(int, int, int, int)':
examination.cpp:52:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = seg[idx].l + seg[idx].r >> 1;
            ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34808 KB Output is correct
2 Correct 36 ms 34816 KB Output is correct
3 Correct 38 ms 34816 KB Output is correct
4 Correct 37 ms 34816 KB Output is correct
5 Correct 43 ms 34808 KB Output is correct
6 Correct 36 ms 34812 KB Output is correct
7 Correct 54 ms 36856 KB Output is correct
8 Correct 54 ms 36856 KB Output is correct
9 Correct 51 ms 36856 KB Output is correct
10 Correct 50 ms 36856 KB Output is correct
11 Correct 44 ms 35712 KB Output is correct
12 Correct 44 ms 35584 KB Output is correct
13 Correct 51 ms 36856 KB Output is correct
14 Correct 52 ms 36856 KB Output is correct
15 Correct 50 ms 36856 KB Output is correct
16 Correct 40 ms 35192 KB Output is correct
17 Correct 48 ms 36856 KB Output is correct
18 Correct 40 ms 35064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2328 ms 118620 KB Output is correct
2 Correct 2324 ms 121176 KB Output is correct
3 Correct 2317 ms 121084 KB Output is correct
4 Correct 1474 ms 120516 KB Output is correct
5 Correct 492 ms 62000 KB Output is correct
6 Correct 360 ms 61292 KB Output is correct
7 Correct 2113 ms 121024 KB Output is correct
8 Correct 2142 ms 121168 KB Output is correct
9 Correct 1835 ms 121016 KB Output is correct
10 Correct 166 ms 45172 KB Output is correct
11 Correct 1102 ms 120308 KB Output is correct
12 Correct 137 ms 44276 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2328 ms 118620 KB Output is correct
2 Correct 2324 ms 121176 KB Output is correct
3 Correct 2317 ms 121084 KB Output is correct
4 Correct 1474 ms 120516 KB Output is correct
5 Correct 492 ms 62000 KB Output is correct
6 Correct 360 ms 61292 KB Output is correct
7 Correct 2113 ms 121024 KB Output is correct
8 Correct 2142 ms 121168 KB Output is correct
9 Correct 1835 ms 121016 KB Output is correct
10 Correct 166 ms 45172 KB Output is correct
11 Correct 1102 ms 120308 KB Output is correct
12 Correct 137 ms 44276 KB Output is correct
13 Correct 2153 ms 121800 KB Output is correct
14 Correct 2387 ms 121488 KB Output is correct
15 Correct 2304 ms 121328 KB Output is correct
16 Correct 1270 ms 120692 KB Output is correct
17 Correct 466 ms 62324 KB Output is correct
18 Correct 391 ms 61428 KB Output is correct
19 Correct 2127 ms 121720 KB Output is correct
20 Correct 2270 ms 121660 KB Output is correct
21 Correct 1969 ms 121584 KB Output is correct
22 Correct 168 ms 45296 KB Output is correct
23 Correct 1116 ms 120412 KB Output is correct
24 Correct 133 ms 44276 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34808 KB Output is correct
2 Correct 36 ms 34816 KB Output is correct
3 Correct 38 ms 34816 KB Output is correct
4 Correct 37 ms 34816 KB Output is correct
5 Correct 43 ms 34808 KB Output is correct
6 Correct 36 ms 34812 KB Output is correct
7 Correct 54 ms 36856 KB Output is correct
8 Correct 54 ms 36856 KB Output is correct
9 Correct 51 ms 36856 KB Output is correct
10 Correct 50 ms 36856 KB Output is correct
11 Correct 44 ms 35712 KB Output is correct
12 Correct 44 ms 35584 KB Output is correct
13 Correct 51 ms 36856 KB Output is correct
14 Correct 52 ms 36856 KB Output is correct
15 Correct 50 ms 36856 KB Output is correct
16 Correct 40 ms 35192 KB Output is correct
17 Correct 48 ms 36856 KB Output is correct
18 Correct 40 ms 35064 KB Output is correct
19 Correct 2328 ms 118620 KB Output is correct
20 Correct 2324 ms 121176 KB Output is correct
21 Correct 2317 ms 121084 KB Output is correct
22 Correct 1474 ms 120516 KB Output is correct
23 Correct 492 ms 62000 KB Output is correct
24 Correct 360 ms 61292 KB Output is correct
25 Correct 2113 ms 121024 KB Output is correct
26 Correct 2142 ms 121168 KB Output is correct
27 Correct 1835 ms 121016 KB Output is correct
28 Correct 166 ms 45172 KB Output is correct
29 Correct 1102 ms 120308 KB Output is correct
30 Correct 137 ms 44276 KB Output is correct
31 Correct 2153 ms 121800 KB Output is correct
32 Correct 2387 ms 121488 KB Output is correct
33 Correct 2304 ms 121328 KB Output is correct
34 Correct 1270 ms 120692 KB Output is correct
35 Correct 466 ms 62324 KB Output is correct
36 Correct 391 ms 61428 KB Output is correct
37 Correct 2127 ms 121720 KB Output is correct
38 Correct 2270 ms 121660 KB Output is correct
39 Correct 1969 ms 121584 KB Output is correct
40 Correct 168 ms 45296 KB Output is correct
41 Correct 1116 ms 120412 KB Output is correct
42 Correct 133 ms 44276 KB Output is correct
43 Correct 2190 ms 126896 KB Output is correct
44 Correct 2203 ms 127092 KB Output is correct
45 Correct 2474 ms 127084 KB Output is correct
46 Correct 1316 ms 125556 KB Output is correct
47 Correct 462 ms 63604 KB Output is correct
48 Correct 330 ms 61172 KB Output is correct
49 Correct 2243 ms 126840 KB Output is correct
50 Correct 1968 ms 126896 KB Output is correct
51 Correct 1882 ms 126620 KB Output is correct
52 Correct 190 ms 46704 KB Output is correct
53 Correct 1076 ms 124292 KB Output is correct