oj.uz

Submission #644252

# Submission time Handle Problem Language Result Execution time Memory
644252 2022-09-24T09:11:12 Z ghostwriter Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1904 ms 196272 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    VOI23 gold medal
*/
const int oo = 2e9 + 5;
const int T = 4e6 + 5;
const int N = 1e6 + 5;
int n, m, w[N], k[N], Max[N][20], LOG[N], ans[N], tr[T], la[T];
vpi d[N];
deque<int> d1;
int get(int l, int r) {
	if (l > r) return -oo;
	int len = LOG[r - l + 1];
	return max(Max[l][len], Max[r - (1 << len) + 1][len]);
}
int lbound(int i, int l, int r, int q) {
	if (l == r) return l;
	int mid = l + (r - l) / 2;
	int pos = tr[i * 2], v = w[pos] + get(mid, pos - 1);
	if (v < 0 || v < w[q] + get(mid, q)) return lbound(i * 2, l, mid, q);
	return lbound(i * 2 + 1, mid + 1, r, q);
}
void lazy(int i, int l, int r) {
	if (!la[i]) return;
	tr[i] = la[i];
	if (l != r) {
		la[i * 2] = la[i];
		la[i * 2 + 1] = la[i];
	}
	la[i] = 0;
}
void upd(int i, int l, int r, int ql, int qr, int v) {
	lazy(i, l, r);
	if (r < ql || l > qr) return;
	if (ql <= l && r <= qr) {
		la[i] = v;
		lazy(i, l, r);
		return;
	}
	int mid = l + (r - l) / 2;
	upd(i * 2, l, mid, ql, qr, v);
	upd(i * 2 + 1, mid + 1, r, ql, qr, v);
	tr[i] = tr[i * 2 + 1];
}
int get(int i, int l, int r, int q) {
	lazy(i, l, r);
	if (r < q || l > q) return 0;
	if (l == r) return tr[i];
	int mid = l + (r - l) / 2;
	return get(i * 2, l, mid, q) + get(i * 2 + 1, mid + 1, r, q);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, n) {
    	cin >> w[i];
    	Max[i][0] = w[i];
    	LOG[i] = log2(i);
    }
    FOR(j, 1, 19)
    FOR(i, 1, n) {
    	if (i + (1 << j) - 1 > n) continue;
    	Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
    }
    FOR(i, 1, m) {
    	int l, r;
    	cin >> l >> r >> k[i];
    	d[r].pb({l, i});
    }
    FOR(i, 1, n << 2) tr[i] = 1;
    w[0] = oo;
    d1.pb(0);
    FOR(i, 2, n) {
    	WHILE(w[d1.bk()] <= w[i]) d1._pb();
    	int l = lbound(1, 1, n, i), r = d1.bk();
    	d1.pb(i);
    	if (l <= r) upd(1, 1, n, l, r, i);
    	EACH(j, d[i]) {
    		int l = j.st, id = j.nd;
    		int pos = get(1, 1, n, l);
    		ans[id] = w[pos] + get(l, pos - 1);
    	}
    }
    // FOR(i, 1, m) {
    // 	debug(i, ans[i]);
    // }
    FOR(i, 1, m) cout << (ans[i] <= k[i]? 1 : 0) << '\n';
    return 0;
}
/*
*/
/*
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:93:5: note: in expansion of macro 'FOR'
   93 |     FOR(i, 1, n) {
      |     ^~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:98:5: note: in expansion of macro 'FOR'
   98 |     FOR(j, 1, 19)
      |     ^~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(i, 1, n) {
      |     ^~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:103:5: note: in expansion of macro 'FOR'
  103 |     FOR(i, 1, m) {
      |     ^~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:108:5: note: in expansion of macro 'FOR'
  108 |     FOR(i, 1, n << 2) tr[i] = 1;
      |     ^~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i, 2, n) {
      |     ^~~
sortbooks.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
sortbooks.cpp:116:6: note: in expansion of macro 'EACH'
  116 |      EACH(j, d[i]) {
      |      ^~~~
sortbooks.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
sortbooks.cpp:125:5: note: in expansion of macro 'FOR'
  125 |     FOR(i, 1, m) cout << (ans[i] <= k[i]? 1 : 0) << '\n';
      |     ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Correct 13 ms 23984 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Correct 13 ms 23984 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 14 ms 24092 KB Output is correct
12 Correct 15 ms 24600 KB Output is correct
13 Correct 16 ms 24600 KB Output is correct
14 Correct 17 ms 24640 KB Output is correct
15 Correct 17 ms 24660 KB Output is correct
16 Correct 16 ms 24660 KB Output is correct
17 Correct 15 ms 24532 KB Output is correct
18 Correct 16 ms 24608 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1797 ms 165724 KB Output is correct
2 Correct 1787 ms 196272 KB Output is correct
3 Correct 1821 ms 196192 KB Output is correct
4 Correct 1904 ms 196244 KB Output is correct
5 Correct 1188 ms 188112 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 39852 KB Output is correct
2 Correct 121 ms 39280 KB Output is correct
3 Correct 88 ms 38632 KB Output is correct
4 Correct 89 ms 38736 KB Output is correct
5 Correct 89 ms 38916 KB Output is correct
6 Correct 79 ms 37984 KB Output is correct
7 Correct 83 ms 37940 KB Output is correct
8 Correct 93 ms 39164 KB Output is correct
9 Correct 51 ms 27212 KB Output is correct
10 Correct 93 ms 39376 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Correct 13 ms 23984 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 14 ms 24092 KB Output is correct
12 Correct 15 ms 24600 KB Output is correct
13 Correct 16 ms 24600 KB Output is correct
14 Correct 17 ms 24640 KB Output is correct
15 Correct 17 ms 24660 KB Output is correct
16 Correct 16 ms 24660 KB Output is correct
17 Correct 15 ms 24532 KB Output is correct
18 Correct 16 ms 24608 KB Output is correct
19 Correct 304 ms 58456 KB Output is correct
20 Correct 306 ms 58444 KB Output is correct
21 Correct 248 ms 57200 KB Output is correct
22 Correct 253 ms 57164 KB Output is correct
23 Correct 278 ms 57236 KB Output is correct
24 Correct 180 ms 54976 KB Output is correct
25 Correct 177 ms 54900 KB Output is correct
26 Correct 196 ms 55680 KB Output is correct
27 Correct 191 ms 55608 KB Output is correct
28 Correct 192 ms 55756 KB Output is correct
29 Correct 209 ms 56388 KB Output is correct
30 Correct 218 ms 56396 KB Output is correct
31 Correct 203 ms 56400 KB Output is correct
32 Correct 227 ms 56448 KB Output is correct
33 Correct 201 ms 56428 KB Output is correct
34 Correct 173 ms 54676 KB Output is correct
35 Correct 178 ms 54800 KB Output is correct
36 Correct 166 ms 54404 KB Output is correct
37 Correct 168 ms 54388 KB Output is correct
38 Correct 177 ms 54636 KB Output is correct
39 Correct 233 ms 56116 KB Output is correct
40 Correct 160 ms 47160 KB Output is correct
41 Correct 220 ms 55872 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23892 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23892 KB Output is correct
7 Correct 13 ms 23984 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 14 ms 24092 KB Output is correct
12 Correct 15 ms 24600 KB Output is correct
13 Correct 16 ms 24600 KB Output is correct
14 Correct 17 ms 24640 KB Output is correct
15 Correct 17 ms 24660 KB Output is correct
16 Correct 16 ms 24660 KB Output is correct
17 Correct 15 ms 24532 KB Output is correct
18 Correct 16 ms 24608 KB Output is correct
19 Correct 1797 ms 165724 KB Output is correct
20 Correct 1787 ms 196272 KB Output is correct
21 Correct 1821 ms 196192 KB Output is correct
22 Correct 1904 ms 196244 KB Output is correct
23 Correct 1188 ms 188112 KB Output is correct
24 Correct 136 ms 39852 KB Output is correct
25 Correct 121 ms 39280 KB Output is correct
26 Correct 88 ms 38632 KB Output is correct
27 Correct 89 ms 38736 KB Output is correct
28 Correct 89 ms 38916 KB Output is correct
29 Correct 79 ms 37984 KB Output is correct
30 Correct 83 ms 37940 KB Output is correct
31 Correct 93 ms 39164 KB Output is correct
32 Correct 51 ms 27212 KB Output is correct
33 Correct 93 ms 39376 KB Output is correct
34 Correct 304 ms 58456 KB Output is correct
35 Correct 306 ms 58444 KB Output is correct
36 Correct 248 ms 57200 KB Output is correct
37 Correct 253 ms 57164 KB Output is correct
38 Correct 278 ms 57236 KB Output is correct
39 Correct 180 ms 54976 KB Output is correct
40 Correct 177 ms 54900 KB Output is correct
41 Correct 196 ms 55680 KB Output is correct
42 Correct 191 ms 55608 KB Output is correct
43 Correct 192 ms 55756 KB Output is correct
44 Correct 209 ms 56388 KB Output is correct
45 Correct 218 ms 56396 KB Output is correct
46 Correct 203 ms 56400 KB Output is correct
47 Correct 227 ms 56448 KB Output is correct
48 Correct 201 ms 56428 KB Output is correct
49 Correct 173 ms 54676 KB Output is correct
50 Correct 178 ms 54800 KB Output is correct
51 Correct 166 ms 54404 KB Output is correct
52 Correct 168 ms 54388 KB Output is correct
53 Correct 177 ms 54636 KB Output is correct
54 Correct 233 ms 56116 KB Output is correct
55 Correct 160 ms 47160 KB Output is correct
56 Correct 220 ms 55872 KB Output is correct
57 Correct 1774 ms 195760 KB Output is correct
58 Correct 1801 ms 195900 KB Output is correct
59 Correct 1684 ms 193000 KB Output is correct
60 Correct 1659 ms 193084 KB Output is correct
61 Correct 1662 ms 193048 KB Output is correct
62 Correct 1720 ms 193096 KB Output is correct
63 Correct 902 ms 179532 KB Output is correct
64 Correct 883 ms 179292 KB Output is correct
65 Correct 1141 ms 184520 KB Output is correct
66 Correct 1107 ms 184428 KB Output is correct
67 Correct 1140 ms 180540 KB Output is correct
68 Correct 1213 ms 179376 KB Output is correct
69 Correct 1231 ms 175592 KB Output is correct
70 Correct 1202 ms 170644 KB Output is correct
71 Correct 1188 ms 170372 KB Output is correct
72 Correct 1185 ms 169708 KB Output is correct
73 Correct 858 ms 176200 KB Output is correct
74 Correct 861 ms 172308 KB Output is correct
75 Correct 827 ms 175992 KB Output is correct
76 Correct 851 ms 167008 KB Output is correct
77 Correct 859 ms 159664 KB Output is correct
78 Correct 1379 ms 185220 KB Output is correct
79 Correct 855 ms 126256 KB Output is correct
80 Correct 1193 ms 183792 KB Output is correct