oj.uz

Submission #429555

# Submission time Handle Problem Language Result Execution time Memory
429555 2021-06-16T06:35:03 Z Return_0 Examination (JOI19_examination) C++17
100 / 100
 2625 ms 114660 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#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;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e5 + 7;

ll A [N], B [N], X [N], Y [N], Z [N], id1 [N], id2 [N], ans [N], n, q;
vector <pll> vec;

struct segtree {
	ll l, r;
	Tree <ll, greater_equal <ll>> t;
	segtree *lt, *rt;
	inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R) {}

	void build () {
		if (l == r) return;
		lt = new segtree (l, mid);
		rt = new segtree (mid + 1, r);
		lt->build();
		rt->build();
	}

	void upd (cl &pos, cl &x) {
		t.insert(x);
		if (l == r) return;
		if (pos <= lt->r) lt->upd(pos, x);
		else rt->upd(pos, x);
	}

	ll ask (cl &ql, cl &x) {
		if (r < ql) return 0;
		if (ql <= l) return t.order_of_key(x - 1);
		return lt->ask(ql, x) + rt->ask(ql, x);
	}
} seg;

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> q;
	for (ll i = 1; i <= n; i++) cin>> A[i] >> B[i], id1[i] = i, vec.push_back({A[i], i});
	for (ll i = 1; i <= q; i++) cin>> X[i] >> Y[i] >> Z[i], id2[i] = i;

	sort(id1 + 1, id1 + n + 1, [&](cl &x, cl &y) { return A[x] + B[x] > A[y] + B[y]; });
	sort(id2 + 1, id2 + q + 1, [&](cl &x, cl &y) { return Z[x] > Z[y]; });
	sort(All(vec));

	seg.r = n; seg.build();
	auto add = [&](cl &v) { seg.upd(upper_bound(All(vec), pll(A[v], v)) - vec.begin(), B[v]); };

	for (ll i = 1, j, ptr = 1; i <= q; i++) {
		j = id2[i];
		while (ptr <= n && A[id1[ptr]] + B[id1[ptr]] >= Z[j]) add(id1[ptr++]);
		ans[j] = seg.ask(lower_bound(All(vec), pll(X[j], 0)) - vec.begin() + 1, Y[j]);
	}

	output(1, q, ans, 0);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 15 ms 2952 KB Output is correct
8 Correct 18 ms 3068 KB Output is correct
9 Correct 19 ms 2988 KB Output is correct
10 Correct 17 ms 2964 KB Output is correct
11 Correct 14 ms 2944 KB Output is correct
12 Correct 12 ms 2936 KB Output is correct
13 Correct 14 ms 3008 KB Output is correct
14 Correct 14 ms 3048 KB Output is correct
15 Correct 14 ms 3004 KB Output is correct
16 Correct 11 ms 2912 KB Output is correct
17 Correct 12 ms 3020 KB Output is correct
18 Correct 9 ms 2892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2456 ms 112256 KB Output is correct
2 Correct 2457 ms 112324 KB Output is correct
3 Correct 2429 ms 112276 KB Output is correct
4 Correct 1470 ms 111556 KB Output is correct
5 Correct 1937 ms 111596 KB Output is correct
6 Correct 1439 ms 110852 KB Output is correct
7 Correct 2232 ms 112108 KB Output is correct
8 Correct 2296 ms 112196 KB Output is correct
9 Correct 1775 ms 112120 KB Output is correct
10 Correct 1444 ms 111284 KB Output is correct
11 Correct 1072 ms 111308 KB Output is correct
12 Correct 495 ms 110432 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2456 ms 112256 KB Output is correct
2 Correct 2457 ms 112324 KB Output is correct
3 Correct 2429 ms 112276 KB Output is correct
4 Correct 1470 ms 111556 KB Output is correct
5 Correct 1937 ms 111596 KB Output is correct
6 Correct 1439 ms 110852 KB Output is correct
7 Correct 2232 ms 112108 KB Output is correct
8 Correct 2296 ms 112196 KB Output is correct
9 Correct 1775 ms 112120 KB Output is correct
10 Correct 1444 ms 111284 KB Output is correct
11 Correct 1072 ms 111308 KB Output is correct
12 Correct 495 ms 110432 KB Output is correct
13 Correct 2160 ms 112712 KB Output is correct
14 Correct 2625 ms 112692 KB Output is correct
15 Correct 2300 ms 112208 KB Output is correct
16 Correct 1262 ms 111808 KB Output is correct
17 Correct 1959 ms 111840 KB Output is correct
18 Correct 1412 ms 110796 KB Output is correct
19 Correct 2076 ms 112684 KB Output is correct
20 Correct 2187 ms 112720 KB Output is correct
21 Correct 1895 ms 112680 KB Output is correct
22 Correct 1429 ms 111360 KB Output is correct
23 Correct 1014 ms 111276 KB Output is correct
24 Correct 497 ms 110400 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 15 ms 2952 KB Output is correct
8 Correct 18 ms 3068 KB Output is correct
9 Correct 19 ms 2988 KB Output is correct
10 Correct 17 ms 2964 KB Output is correct
11 Correct 14 ms 2944 KB Output is correct
12 Correct 12 ms 2936 KB Output is correct
13 Correct 14 ms 3008 KB Output is correct
14 Correct 14 ms 3048 KB Output is correct
15 Correct 14 ms 3004 KB Output is correct
16 Correct 11 ms 2912 KB Output is correct
17 Correct 12 ms 3020 KB Output is correct
18 Correct 9 ms 2892 KB Output is correct
19 Correct 2456 ms 112256 KB Output is correct
20 Correct 2457 ms 112324 KB Output is correct
21 Correct 2429 ms 112276 KB Output is correct
22 Correct 1470 ms 111556 KB Output is correct
23 Correct 1937 ms 111596 KB Output is correct
24 Correct 1439 ms 110852 KB Output is correct
25 Correct 2232 ms 112108 KB Output is correct
26 Correct 2296 ms 112196 KB Output is correct
27 Correct 1775 ms 112120 KB Output is correct
28 Correct 1444 ms 111284 KB Output is correct
29 Correct 1072 ms 111308 KB Output is correct
30 Correct 495 ms 110432 KB Output is correct
31 Correct 2160 ms 112712 KB Output is correct
32 Correct 2625 ms 112692 KB Output is correct
33 Correct 2300 ms 112208 KB Output is correct
34 Correct 1262 ms 111808 KB Output is correct
35 Correct 1959 ms 111840 KB Output is correct
36 Correct 1412 ms 110796 KB Output is correct
37 Correct 2076 ms 112684 KB Output is correct
38 Correct 2187 ms 112720 KB Output is correct
39 Correct 1895 ms 112680 KB Output is correct
40 Correct 1429 ms 111360 KB Output is correct
41 Correct 1014 ms 111276 KB Output is correct
42 Correct 497 ms 110400 KB Output is correct
43 Correct 2085 ms 114660 KB Output is correct
44 Correct 2208 ms 114620 KB Output is correct
45 Correct 2394 ms 114520 KB Output is correct
46 Correct 1234 ms 113132 KB Output is correct
47 Correct 1996 ms 113104 KB Output is correct
48 Correct 1202 ms 110556 KB Output is correct
49 Correct 2363 ms 114632 KB Output is correct
50 Correct 2143 ms 114484 KB Output is correct
51 Correct 1949 ms 114452 KB Output is correct
52 Correct 1540 ms 112864 KB Output is correct
53 Correct 1061 ms 112140 KB Output is correct