oj.uz

Submission #497879

# Submission time Handle Problem Language Result Execution time Memory
497879 2021-12-24T03:36:17 Z armashka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1378 ms 124916 KB 
#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            

ll n, m, a[N], t[N * 4], ans[N];
vector <pair<pll, ll>> q[N];
vector <ll> v;

void upd(ll pos, ll val, ll v = 1, ll tl = 1, ll tr = n) {
	if (tl == tr) {
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (pos <= tm) upd(pos, val, v + v, tl, tm);
	else upd(pos, val, v + v + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
}

ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
	if (r < tl || tr < l) return 0;
	if (l <= tl && tr <= r) return t[v];
	ll tm = (tl + tr) / 2;
	return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

const void solve(/*Armashka*/) {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= m; ++ i) {
		ll l, r, k;
		cin >> l >> r >> k;
		q[r].pb({{l, k}, i});
	}
	v.pb(0);
	for (int i = 1; i <= n; ++ i) {
		while (v.back() > 0 && a[v.back()] <= a[i]) v.pop_back();
		if (v.back() > 0) upd(v.back(), a[v.back()] + a[i]);
		v.pb(i);
		while (q[i].sz) {
			ll l = q[i].back().ft.ft, r = i, k = q[i].back().ft.sd, id = q[i].back().sd;
			q[i].pop_back();
			if (get(l, r) <= k) ans[id] = 1;
		}
	}
	for (int i = 1; i <= m; ++ i) cout << ans[i] << "\n";	
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt --) {                                                
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23708 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 13 ms 23836 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23812 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 15 ms 23808 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23708 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 13 ms 23836 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23812 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 15 ms 23808 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 17 ms 24064 KB Output is correct
13 Correct 17 ms 24132 KB Output is correct
14 Correct 22 ms 24304 KB Output is correct
15 Correct 21 ms 24224 KB Output is correct
16 Correct 18 ms 24240 KB Output is correct
17 Correct 15 ms 24200 KB Output is correct
18 Correct 17 ms 24076 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1292 ms 82456 KB Output is correct
2 Correct 1354 ms 82616 KB Output is correct
3 Correct 1297 ms 82580 KB Output is correct
4 Correct 1321 ms 82552 KB Output is correct
5 Correct 1194 ms 73988 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 30788 KB Output is correct
2 Correct 104 ms 33040 KB Output is correct
3 Correct 92 ms 30836 KB Output is correct
4 Correct 100 ms 30800 KB Output is correct
5 Correct 95 ms 30796 KB Output is correct
6 Correct 88 ms 30024 KB Output is correct
7 Correct 79 ms 29936 KB Output is correct
8 Correct 85 ms 30228 KB Output is correct
9 Correct 57 ms 29048 KB Output is correct
10 Correct 86 ms 30244 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23708 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 13 ms 23836 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23812 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 15 ms 23808 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 17 ms 24064 KB Output is correct
13 Correct 17 ms 24132 KB Output is correct
14 Correct 22 ms 24304 KB Output is correct
15 Correct 21 ms 24224 KB Output is correct
16 Correct 18 ms 24240 KB Output is correct
17 Correct 15 ms 24200 KB Output is correct
18 Correct 17 ms 24076 KB Output is correct
19 Correct 248 ms 44564 KB Output is correct
20 Correct 230 ms 44484 KB Output is correct
21 Correct 213 ms 44928 KB Output is correct
22 Correct 198 ms 44860 KB Output is correct
23 Correct 193 ms 44916 KB Output is correct
24 Correct 176 ms 40836 KB Output is correct
25 Correct 242 ms 40796 KB Output is correct
26 Correct 187 ms 40660 KB Output is correct
27 Correct 181 ms 40704 KB Output is correct
28 Correct 198 ms 40516 KB Output is correct
29 Correct 208 ms 40440 KB Output is correct
30 Correct 196 ms 40388 KB Output is correct
31 Correct 242 ms 40380 KB Output is correct
32 Correct 208 ms 40368 KB Output is correct
33 Correct 232 ms 40392 KB Output is correct
34 Correct 160 ms 40240 KB Output is correct
35 Correct 170 ms 40192 KB Output is correct
36 Correct 154 ms 40108 KB Output is correct
37 Correct 151 ms 40056 KB Output is correct
38 Correct 157 ms 40140 KB Output is correct
39 Correct 181 ms 40004 KB Output is correct
40 Correct 142 ms 36764 KB Output is correct
41 Correct 196 ms 38072 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23708 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 13 ms 23836 KB Output is correct
4 Correct 13 ms 23848 KB Output is correct
5 Correct 16 ms 23792 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23812 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 15 ms 23808 KB Output is correct
10 Correct 13 ms 23784 KB Output is correct
11 Correct 16 ms 24012 KB Output is correct
12 Correct 17 ms 24064 KB Output is correct
13 Correct 17 ms 24132 KB Output is correct
14 Correct 22 ms 24304 KB Output is correct
15 Correct 21 ms 24224 KB Output is correct
16 Correct 18 ms 24240 KB Output is correct
17 Correct 15 ms 24200 KB Output is correct
18 Correct 17 ms 24076 KB Output is correct
19 Correct 1292 ms 82456 KB Output is correct
20 Correct 1354 ms 82616 KB Output is correct
21 Correct 1297 ms 82580 KB Output is correct
22 Correct 1321 ms 82552 KB Output is correct
23 Correct 1194 ms 73988 KB Output is correct
24 Correct 107 ms 30788 KB Output is correct
25 Correct 104 ms 33040 KB Output is correct
26 Correct 92 ms 30836 KB Output is correct
27 Correct 100 ms 30800 KB Output is correct
28 Correct 95 ms 30796 KB Output is correct
29 Correct 88 ms 30024 KB Output is correct
30 Correct 79 ms 29936 KB Output is correct
31 Correct 85 ms 30228 KB Output is correct
32 Correct 57 ms 29048 KB Output is correct
33 Correct 86 ms 30244 KB Output is correct
34 Correct 248 ms 44564 KB Output is correct
35 Correct 230 ms 44484 KB Output is correct
36 Correct 213 ms 44928 KB Output is correct
37 Correct 198 ms 44860 KB Output is correct
38 Correct 193 ms 44916 KB Output is correct
39 Correct 176 ms 40836 KB Output is correct
40 Correct 242 ms 40796 KB Output is correct
41 Correct 187 ms 40660 KB Output is correct
42 Correct 181 ms 40704 KB Output is correct
43 Correct 198 ms 40516 KB Output is correct
44 Correct 208 ms 40440 KB Output is correct
45 Correct 196 ms 40388 KB Output is correct
46 Correct 242 ms 40380 KB Output is correct
47 Correct 208 ms 40368 KB Output is correct
48 Correct 232 ms 40392 KB Output is correct
49 Correct 160 ms 40240 KB Output is correct
50 Correct 170 ms 40192 KB Output is correct
51 Correct 154 ms 40108 KB Output is correct
52 Correct 151 ms 40056 KB Output is correct
53 Correct 157 ms 40140 KB Output is correct
54 Correct 181 ms 40004 KB Output is correct
55 Correct 142 ms 36764 KB Output is correct
56 Correct 196 ms 38072 KB Output is correct
57 Correct 1369 ms 124064 KB Output is correct
58 Correct 1316 ms 124000 KB Output is correct
59 Correct 1286 ms 124712 KB Output is correct
60 Correct 1345 ms 124760 KB Output is correct
61 Correct 1269 ms 124888 KB Output is correct
62 Correct 1378 ms 124916 KB Output is correct
63 Correct 872 ms 108476 KB Output is correct
64 Correct 937 ms 108616 KB Output is correct
65 Correct 1177 ms 108452 KB Output is correct
66 Correct 1105 ms 108440 KB Output is correct
67 Correct 1113 ms 108372 KB Output is correct
68 Correct 1126 ms 107564 KB Output is correct
69 Correct 1130 ms 107584 KB Output is correct
70 Correct 1126 ms 107740 KB Output is correct
71 Correct 1178 ms 107780 KB Output is correct
72 Correct 1216 ms 107700 KB Output is correct
73 Correct 774 ms 102496 KB Output is correct
74 Correct 820 ms 103404 KB Output is correct
75 Correct 808 ms 102280 KB Output is correct
76 Correct 750 ms 102940 KB Output is correct
77 Correct 749 ms 102572 KB Output is correct
78 Correct 988 ms 104572 KB Output is correct
79 Correct 678 ms 88044 KB Output is correct
80 Correct 919 ms 95404 KB Output is correct