oj.uz

Submission #289670

# Submission time Handle Problem Language Result Execution time Memory
289670 2020-09-02T22:21:19 Z eggag32 Examination (JOI19_examination) C++17
100 / 100
 2353 ms 159096 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
#define ar array
const int mxN = 1e5 + 5;
 
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
 
template<class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
 
int n, q;
 
bool cmp(pair<pi, int> a, pair<pi, int> b){
	return (a.fi.fi + a.fi.se) < (b.fi.fi + b.fi.se);
}
 
bool cmp1(pair<pi, int> a, pair<pi, int> b){
	return a.fi.fi > b.fi.fi;
}
 
bool cmp2(ar<int, 4> a, ar<int, 4> b){
	return a[0] > b[0];
}
 
//segment tree
 
ordered_set<pi> t[4 * mxN];
int a[mxN];
 
int query(int v, int tl, int tr, int l, int r, int x){
	if(l > r) return 0;
	if(l == tl && r == tr){
		return (t[v].size() - t[v].order_of_key({x, -1}));
	}
	int tm = (tl + tr) / 2;
	return query(v * 2, tl, tm, l, min(r, tm), x) + query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
}
 
void update(int v, int tl, int tr, int pos, int new_val){
	t[v].insert({new_val, pos});
	if(tl != tr){
		int tm = (tl + tr) / 2;
		if(pos <= tm) update(v * 2, tl, tm, pos, new_val);
		else update(v * 2 + 1, tm + 1, tr, pos, new_val);
	}
	else a[pos] = new_val;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin >> n >> q;
	vector<pair<pi, int>> p(n);
	rep(i, n) cin >> p[i].fi.fi >> p[i].fi.se;
	sort(all(p), cmp);
	rep(i, n) p[i].se = i;
	vector<pair<pi, int>> p1 = p;
	sort(all(p), cmp1);
	vector<ar<int, 4>> ask(q);
	rep(i, q) cin >> ask[i][0] >> ask[i][1] >> ask[i][2];
	//sort the queries by a
	rep(i, q) ask[i][3] = i;
	sort(all(ask), cmp2);
	rep(i, n) a[p1[i].se] = p1[i].fi.se;
	vi ans(q, 0);
	int cur = 0;
	rep(i, q){
		//do all the updates
		while(cur < n && p[cur].fi.fi >= ask[i][0]){
			update(1, 0, n - 1, p[cur].se, p[cur].fi.se);
			cur++;
		}
		//find the lo (the first one not less than c)
		int l = 0, r = n - 1;
		while(l < r){
			int mid = (l + r) / 2;
			if((p1[mid].fi.fi + p1[mid].fi.se) >= ask[i][2]) r = mid;
			else l = mid + 1;
		}
		if(p1[l].fi.fi + p1[l].fi.se >= ask[i][2]){
			ans[ask[i][3]] = query(1, 0, n - 1, l, n - 1, ask[i][1]);
		}
	}
	rep(i, q) cout << ans[i] << '\n';
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37880 KB Output is correct
2 Correct 39 ms 37880 KB Output is correct
3 Correct 39 ms 37880 KB Output is correct
4 Correct 39 ms 37880 KB Output is correct
5 Correct 39 ms 37880 KB Output is correct
6 Correct 39 ms 37888 KB Output is correct
7 Correct 56 ms 40440 KB Output is correct
8 Correct 55 ms 40440 KB Output is correct
9 Correct 56 ms 40440 KB Output is correct
10 Correct 55 ms 40440 KB Output is correct
11 Correct 56 ms 40576 KB Output is correct
12 Correct 55 ms 40572 KB Output is correct
13 Correct 54 ms 40568 KB Output is correct
14 Correct 54 ms 40568 KB Output is correct
15 Correct 54 ms 40568 KB Output is correct
16 Correct 54 ms 40572 KB Output is correct
17 Correct 55 ms 40600 KB Output is correct
18 Correct 51 ms 40444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1757 ms 154104 KB Output is correct
2 Correct 1740 ms 156408 KB Output is correct
3 Correct 1713 ms 156520 KB Output is correct
4 Correct 845 ms 155896 KB Output is correct
5 Correct 1020 ms 155768 KB Output is correct
6 Correct 958 ms 155000 KB Output is correct
7 Correct 1707 ms 156572 KB Output is correct
8 Correct 1713 ms 156472 KB Output is correct
9 Correct 1646 ms 156424 KB Output is correct
10 Correct 785 ms 155512 KB Output is correct
11 Correct 784 ms 155512 KB Output is correct
12 Correct 720 ms 154768 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1757 ms 154104 KB Output is correct
2 Correct 1740 ms 156408 KB Output is correct
3 Correct 1713 ms 156520 KB Output is correct
4 Correct 845 ms 155896 KB Output is correct
5 Correct 1020 ms 155768 KB Output is correct
6 Correct 958 ms 155000 KB Output is correct
7 Correct 1707 ms 156572 KB Output is correct
8 Correct 1713 ms 156472 KB Output is correct
9 Correct 1646 ms 156424 KB Output is correct
10 Correct 785 ms 155512 KB Output is correct
11 Correct 784 ms 155512 KB Output is correct
12 Correct 720 ms 154768 KB Output is correct
13 Correct 2098 ms 157088 KB Output is correct
14 Correct 2086 ms 156920 KB Output is correct
15 Correct 1721 ms 156536 KB Output is correct
16 Correct 1362 ms 156384 KB Output is correct
17 Correct 1306 ms 156280 KB Output is correct
18 Correct 1054 ms 155252 KB Output is correct
19 Correct 2111 ms 157060 KB Output is correct
20 Correct 2140 ms 156952 KB Output is correct
21 Correct 2162 ms 157004 KB Output is correct
22 Correct 771 ms 155640 KB Output is correct
23 Correct 776 ms 155592 KB Output is correct
24 Correct 726 ms 154744 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37880 KB Output is correct
2 Correct 39 ms 37880 KB Output is correct
3 Correct 39 ms 37880 KB Output is correct
4 Correct 39 ms 37880 KB Output is correct
5 Correct 39 ms 37880 KB Output is correct
6 Correct 39 ms 37888 KB Output is correct
7 Correct 56 ms 40440 KB Output is correct
8 Correct 55 ms 40440 KB Output is correct
9 Correct 56 ms 40440 KB Output is correct
10 Correct 55 ms 40440 KB Output is correct
11 Correct 56 ms 40576 KB Output is correct
12 Correct 55 ms 40572 KB Output is correct
13 Correct 54 ms 40568 KB Output is correct
14 Correct 54 ms 40568 KB Output is correct
15 Correct 54 ms 40568 KB Output is correct
16 Correct 54 ms 40572 KB Output is correct
17 Correct 55 ms 40600 KB Output is correct
18 Correct 51 ms 40444 KB Output is correct
19 Correct 1757 ms 154104 KB Output is correct
20 Correct 1740 ms 156408 KB Output is correct
21 Correct 1713 ms 156520 KB Output is correct
22 Correct 845 ms 155896 KB Output is correct
23 Correct 1020 ms 155768 KB Output is correct
24 Correct 958 ms 155000 KB Output is correct
25 Correct 1707 ms 156572 KB Output is correct
26 Correct 1713 ms 156472 KB Output is correct
27 Correct 1646 ms 156424 KB Output is correct
28 Correct 785 ms 155512 KB Output is correct
29 Correct 784 ms 155512 KB Output is correct
30 Correct 720 ms 154768 KB Output is correct
31 Correct 2098 ms 157088 KB Output is correct
32 Correct 2086 ms 156920 KB Output is correct
33 Correct 1721 ms 156536 KB Output is correct
34 Correct 1362 ms 156384 KB Output is correct
35 Correct 1306 ms 156280 KB Output is correct
36 Correct 1054 ms 155252 KB Output is correct
37 Correct 2111 ms 157060 KB Output is correct
38 Correct 2140 ms 156952 KB Output is correct
39 Correct 2162 ms 157004 KB Output is correct
40 Correct 771 ms 155640 KB Output is correct
41 Correct 776 ms 155592 KB Output is correct
42 Correct 726 ms 154744 KB Output is correct
43 Correct 2105 ms 158964 KB Output is correct
44 Correct 2134 ms 159096 KB Output is correct
45 Correct 2036 ms 159096 KB Output is correct
46 Correct 1352 ms 157292 KB Output is correct
47 Correct 1293 ms 157432 KB Output is correct
48 Correct 1016 ms 155000 KB Output is correct
49 Correct 2353 ms 158840 KB Output is correct
50 Correct 2035 ms 158712 KB Output is correct
51 Correct 2121 ms 158912 KB Output is correct
52 Correct 982 ms 157216 KB Output is correct
53 Correct 773 ms 156408 KB Output is correct