oj.uz

Submission #206807

# Submission time Handle Problem Language Result Execution time Memory
206807 2020-03-05T13:07:16 Z bash Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1600 ms 75496 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}

struct query {
	int l, r, x, id;
};


int n, m;
int a[MAXN];
///int lim[MAXN];
int t[MAXN*4];
int ans[MAXN];
int used[MAXN];
/*
void build(int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = lim[tl];
		return;
	}
	int tm = (tl + tr)/ 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
}
*/
int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	if (r < tl || tr < l) {
		return 0;
	}
	int tm = (tl + tr) / 2;
	return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

void update(int pos, int x, int v = 1, int tl = 1, int tr = n) {
	if (tl == tr) {
		t[v] = max(t[v], x);
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		update(pos, x, v * 2, tl, tm);
	} else {
		update(pos, x, v * 2 + 1, tm + 1, tr);		
	}
	t[v] = max(t[v* 2], t[v * 2 + 1]);
}

bool cmp(const query &a, const query &b) {
	if (a.r == b.r) {
		return a.l < b.l;		
	}
	return a.r < b.r;
}

vector<query> Q[MAXN];

int main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
	n = readInt(), m = readInt();
    for (int i = 1; i <= n; i++) {
    	a[i] = readInt();
    }
    stack <int> kek; /// pos
    for (int i = 1; i <= n; i++) {
		while(!kek.empty() && a[kek.top()] <= a[i]) {
			kek.pop();
		}
		if (!kek.empty()) {
			int pos = kek.top();
			///lim[pos] = max(lim[pos], a[i] + a[pos]);
			used[i] = pos;
		}
		kek.push(i);    	
    }
    for (int i = 1; i <= m; i++) {
		query tmp;
		tmp.l = readInt(), tmp.r = readInt(), tmp.x = readInt();
		tmp.id = i;
		Q[tmp.r].pb(tmp);
    }
    for (int i = 1; i <= n; i++) {
		if (used[i]) {
			update(used[i], a[i] + a[used[i]]);
		}    	
		for (query cur : Q[i]) {
			int L = cur.l;
    		int R = cur.r;
	    	int X = cur.x;
    		ans[cur.id] = (get(L, R) <= X);
		}
    }
    for (int i = 1; i <= m; i++) {
    	cout << ans[i] << endl;
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 20 ms 23824 KB Output is correct
3 Correct 20 ms 23928 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 20 ms 23800 KB Output is correct
6 Correct 19 ms 23928 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 20 ms 23928 KB Output is correct
9 Correct 21 ms 23928 KB Output is correct
10 Correct 20 ms 23800 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 20 ms 23824 KB Output is correct
3 Correct 20 ms 23928 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 20 ms 23800 KB Output is correct
6 Correct 19 ms 23928 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 20 ms 23928 KB Output is correct
9 Correct 21 ms 23928 KB Output is correct
10 Correct 20 ms 23800 KB Output is correct
11 Correct 22 ms 24056 KB Output is correct
12 Correct 22 ms 24056 KB Output is correct
13 Correct 22 ms 24184 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 22 ms 24056 KB Output is correct
18 Correct 22 ms 24056 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 71976 KB Output is correct
2 Correct 1552 ms 75384 KB Output is correct
3 Correct 1600 ms 75256 KB Output is correct
4 Correct 1595 ms 75384 KB Output is correct
5 Correct 1302 ms 63224 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 28792 KB Output is correct
2 Correct 103 ms 30584 KB Output is correct
3 Correct 97 ms 29304 KB Output is correct
4 Correct 97 ms 29432 KB Output is correct
5 Correct 95 ms 29304 KB Output is correct
6 Correct 80 ms 28920 KB Output is correct
7 Correct 79 ms 28920 KB Output is correct
8 Correct 91 ms 29164 KB Output is correct
9 Correct 55 ms 27628 KB Output is correct
10 Correct 85 ms 29036 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 20 ms 23824 KB Output is correct
3 Correct 20 ms 23928 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 20 ms 23800 KB Output is correct
6 Correct 19 ms 23928 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 20 ms 23928 KB Output is correct
9 Correct 21 ms 23928 KB Output is correct
10 Correct 20 ms 23800 KB Output is correct
11 Correct 22 ms 24056 KB Output is correct
12 Correct 22 ms 24056 KB Output is correct
13 Correct 22 ms 24184 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 22 ms 24056 KB Output is correct
18 Correct 22 ms 24056 KB Output is correct
19 Correct 263 ms 39800 KB Output is correct
20 Correct 271 ms 39796 KB Output is correct
21 Correct 237 ms 39496 KB Output is correct
22 Correct 221 ms 39416 KB Output is correct
23 Correct 222 ms 39288 KB Output is correct
24 Correct 192 ms 36344 KB Output is correct
25 Correct 186 ms 36344 KB Output is correct
26 Correct 215 ms 36600 KB Output is correct
27 Correct 215 ms 36600 KB Output is correct
28 Correct 214 ms 36652 KB Output is correct
29 Correct 234 ms 36812 KB Output is correct
30 Correct 240 ms 36916 KB Output is correct
31 Correct 237 ms 36688 KB Output is correct
32 Correct 234 ms 36684 KB Output is correct
33 Correct 240 ms 36728 KB Output is correct
34 Correct 177 ms 35984 KB Output is correct
35 Correct 176 ms 35984 KB Output is correct
36 Correct 178 ms 36216 KB Output is correct
37 Correct 174 ms 36012 KB Output is correct
38 Correct 176 ms 36068 KB Output is correct
39 Correct 206 ms 36716 KB Output is correct
40 Correct 156 ms 34532 KB Output is correct
41 Correct 196 ms 35688 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 20 ms 23824 KB Output is correct
3 Correct 20 ms 23928 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 20 ms 23800 KB Output is correct
6 Correct 19 ms 23928 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 20 ms 23928 KB Output is correct
9 Correct 21 ms 23928 KB Output is correct
10 Correct 20 ms 23800 KB Output is correct
11 Correct 22 ms 24056 KB Output is correct
12 Correct 22 ms 24056 KB Output is correct
13 Correct 22 ms 24184 KB Output is correct
14 Correct 24 ms 24184 KB Output is correct
15 Correct 24 ms 24184 KB Output is correct
16 Correct 23 ms 24184 KB Output is correct
17 Correct 22 ms 24056 KB Output is correct
18 Correct 22 ms 24056 KB Output is correct
19 Correct 1578 ms 71976 KB Output is correct
20 Correct 1552 ms 75384 KB Output is correct
21 Correct 1600 ms 75256 KB Output is correct
22 Correct 1595 ms 75384 KB Output is correct
23 Correct 1302 ms 63224 KB Output is correct
24 Correct 115 ms 28792 KB Output is correct
25 Correct 103 ms 30584 KB Output is correct
26 Correct 97 ms 29304 KB Output is correct
27 Correct 97 ms 29432 KB Output is correct
28 Correct 95 ms 29304 KB Output is correct
29 Correct 80 ms 28920 KB Output is correct
30 Correct 79 ms 28920 KB Output is correct
31 Correct 91 ms 29164 KB Output is correct
32 Correct 55 ms 27628 KB Output is correct
33 Correct 85 ms 29036 KB Output is correct
34 Correct 263 ms 39800 KB Output is correct
35 Correct 271 ms 39796 KB Output is correct
36 Correct 237 ms 39496 KB Output is correct
37 Correct 221 ms 39416 KB Output is correct
38 Correct 222 ms 39288 KB Output is correct
39 Correct 192 ms 36344 KB Output is correct
40 Correct 186 ms 36344 KB Output is correct
41 Correct 215 ms 36600 KB Output is correct
42 Correct 215 ms 36600 KB Output is correct
43 Correct 214 ms 36652 KB Output is correct
44 Correct 234 ms 36812 KB Output is correct
45 Correct 240 ms 36916 KB Output is correct
46 Correct 237 ms 36688 KB Output is correct
47 Correct 234 ms 36684 KB Output is correct
48 Correct 240 ms 36728 KB Output is correct
49 Correct 177 ms 35984 KB Output is correct
50 Correct 176 ms 35984 KB Output is correct
51 Correct 178 ms 36216 KB Output is correct
52 Correct 174 ms 36012 KB Output is correct
53 Correct 176 ms 36068 KB Output is correct
54 Correct 206 ms 36716 KB Output is correct
55 Correct 156 ms 34532 KB Output is correct
56 Correct 196 ms 35688 KB Output is correct
57 Correct 1580 ms 75496 KB Output is correct
58 Correct 1553 ms 75356 KB Output is correct
59 Correct 1490 ms 74380 KB Output is correct
60 Correct 1473 ms 74664 KB Output is correct
61 Correct 1506 ms 74352 KB Output is correct
62 Correct 1482 ms 74432 KB Output is correct
63 Correct 906 ms 60664 KB Output is correct
64 Correct 886 ms 60536 KB Output is correct
65 Correct 1254 ms 62200 KB Output is correct
66 Correct 1214 ms 61944 KB Output is correct
67 Correct 1216 ms 61724 KB Output is correct
68 Correct 1268 ms 62224 KB Output is correct
69 Correct 1287 ms 61944 KB Output is correct
70 Correct 1294 ms 61712 KB Output is correct
71 Correct 1277 ms 61564 KB Output is correct
72 Correct 1291 ms 61360 KB Output is correct
73 Correct 821 ms 55928 KB Output is correct
74 Correct 834 ms 56036 KB Output is correct
75 Correct 830 ms 55800 KB Output is correct
76 Correct 833 ms 55892 KB Output is correct
77 Correct 822 ms 55544 KB Output is correct
78 Correct 1123 ms 62452 KB Output is correct
79 Correct 810 ms 54736 KB Output is correct
80 Correct 1048 ms 61008 KB Output is correct