oj.uz

Submission #684488

# Submission time Handle Problem Language Result Execution time Memory
684488 2023-01-21T10:48:56 Z Chal1shkan Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1242 ms 92564 KB 
# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e6 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;
 
struct query
{
	ll L, K, ID;
	query (ll x, ll y, ll z)
	{
		L = x;
		K = y;
		ID = z;
	}
};
 
vector <query> q[maxn];
 
ll n, m, a[maxn];
ll t[maxn * 4];
ll ans[maxn];
 
void update (ll pos, ll x, ll v = 1, ll tl = 1, ll tr = n)
{
	if (tl == tr)
	{
		t[v] = max(t[v], x);
		return;
	}
	ll tm = (tl + tr) >> 1;
	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]);
}
 
ll get (ll l, ll r, ll v = 1, ll tl = 1, ll tr = n)
{
	if (tr < l || r < tl) return 0;
	if (l <= tl && tr <= r) return t[v];
	ll tm = (tl + tr) >> 1;
	return max(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
}
 
void ma1n (/* SABR */)
{
	cin >> n >> m;
	for (ll i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	for (ll i = 1; i <= m; ++i)
	{
		ll l, r, k;
		cin >> l >> r >> k;
		q[r].pb({l, k, i});
	}
	vector <ll> v;
	for (ll r = 1; r <= n; ++r)
	{
		while (!v.empty() && a[v.back()] <= a[r]) v.pop_back();
		if (!v.empty())
		{
			update(v.back(), a[r] + a[v.back()]); 
		}
		for (query i : q[r])
		{
			ll l = i.L, k = i.K, id = i.ID;
			if (get(l, r) <= k)
			{ 
				ans[id] = 1;
			}
		}
		v.pb(r);
	}
	for (ll i = 1; i <= m; ++i) cout << ans[i] << nl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

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 23716 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 15 ms 23784 KB Output is correct
7 Correct 13 ms 23828 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 12 ms 24016 KB Output is correct
10 Correct 12 ms 23764 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 23716 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 15 ms 23784 KB Output is correct
7 Correct 13 ms 23828 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 12 ms 24016 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 14 ms 23956 KB Output is correct
12 Correct 15 ms 24148 KB Output is correct
13 Correct 16 ms 24148 KB Output is correct
14 Correct 17 ms 24276 KB Output is correct
15 Correct 17 ms 24276 KB Output is correct
16 Correct 16 ms 24148 KB Output is correct
17 Correct 15 ms 24208 KB Output is correct
18 Correct 16 ms 24156 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 83640 KB Output is correct
2 Correct 1191 ms 83544 KB Output is correct
3 Correct 1189 ms 83480 KB Output is correct
4 Correct 1206 ms 83524 KB Output is correct
5 Correct 1025 ms 75004 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 31760 KB Output is correct
2 Correct 97 ms 31968 KB Output is correct
3 Correct 82 ms 29744 KB Output is correct
4 Correct 80 ms 29680 KB Output is correct
5 Correct 86 ms 29676 KB Output is correct
6 Correct 69 ms 29100 KB Output is correct
7 Correct 70 ms 29000 KB Output is correct
8 Correct 74 ms 29484 KB Output is correct
9 Correct 48 ms 28648 KB Output is correct
10 Correct 78 ms 29392 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 23716 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 15 ms 23784 KB Output is correct
7 Correct 13 ms 23828 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 12 ms 24016 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 14 ms 23956 KB Output is correct
12 Correct 15 ms 24148 KB Output is correct
13 Correct 16 ms 24148 KB Output is correct
14 Correct 17 ms 24276 KB Output is correct
15 Correct 17 ms 24276 KB Output is correct
16 Correct 16 ms 24148 KB Output is correct
17 Correct 15 ms 24208 KB Output is correct
18 Correct 16 ms 24156 KB Output is correct
19 Correct 211 ms 38780 KB Output is correct
20 Correct 219 ms 38848 KB Output is correct
21 Correct 179 ms 39420 KB Output is correct
22 Correct 196 ms 39420 KB Output is correct
23 Correct 178 ms 39424 KB Output is correct
24 Correct 153 ms 35452 KB Output is correct
25 Correct 156 ms 35540 KB Output is correct
26 Correct 176 ms 35064 KB Output is correct
27 Correct 169 ms 35028 KB Output is correct
28 Correct 176 ms 34952 KB Output is correct
29 Correct 182 ms 34772 KB Output is correct
30 Correct 182 ms 34748 KB Output is correct
31 Correct 195 ms 34760 KB Output is correct
32 Correct 179 ms 34764 KB Output is correct
33 Correct 183 ms 34764 KB Output is correct
34 Correct 143 ms 34956 KB Output is correct
35 Correct 147 ms 34824 KB Output is correct
36 Correct 142 ms 34888 KB Output is correct
37 Correct 151 ms 34952 KB Output is correct
38 Correct 148 ms 34940 KB Output is correct
39 Correct 157 ms 35636 KB Output is correct
40 Correct 124 ms 33272 KB Output is correct
41 Correct 165 ms 34092 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 23716 KB Output is correct
3 Correct 12 ms 23808 KB Output is correct
4 Correct 12 ms 23824 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 15 ms 23784 KB Output is correct
7 Correct 13 ms 23828 KB Output is correct
8 Correct 13 ms 23816 KB Output is correct
9 Correct 12 ms 24016 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 14 ms 23956 KB Output is correct
12 Correct 15 ms 24148 KB Output is correct
13 Correct 16 ms 24148 KB Output is correct
14 Correct 17 ms 24276 KB Output is correct
15 Correct 17 ms 24276 KB Output is correct
16 Correct 16 ms 24148 KB Output is correct
17 Correct 15 ms 24208 KB Output is correct
18 Correct 16 ms 24156 KB Output is correct
19 Correct 1242 ms 83640 KB Output is correct
20 Correct 1191 ms 83544 KB Output is correct
21 Correct 1189 ms 83480 KB Output is correct
22 Correct 1206 ms 83524 KB Output is correct
23 Correct 1025 ms 75004 KB Output is correct
24 Correct 114 ms 31760 KB Output is correct
25 Correct 97 ms 31968 KB Output is correct
26 Correct 82 ms 29744 KB Output is correct
27 Correct 80 ms 29680 KB Output is correct
28 Correct 86 ms 29676 KB Output is correct
29 Correct 69 ms 29100 KB Output is correct
30 Correct 70 ms 29000 KB Output is correct
31 Correct 74 ms 29484 KB Output is correct
32 Correct 48 ms 28648 KB Output is correct
33 Correct 78 ms 29392 KB Output is correct
34 Correct 211 ms 38780 KB Output is correct
35 Correct 219 ms 38848 KB Output is correct
36 Correct 179 ms 39420 KB Output is correct
37 Correct 196 ms 39420 KB Output is correct
38 Correct 178 ms 39424 KB Output is correct
39 Correct 153 ms 35452 KB Output is correct
40 Correct 156 ms 35540 KB Output is correct
41 Correct 176 ms 35064 KB Output is correct
42 Correct 169 ms 35028 KB Output is correct
43 Correct 176 ms 34952 KB Output is correct
44 Correct 182 ms 34772 KB Output is correct
45 Correct 182 ms 34748 KB Output is correct
46 Correct 195 ms 34760 KB Output is correct
47 Correct 179 ms 34764 KB Output is correct
48 Correct 183 ms 34764 KB Output is correct
49 Correct 143 ms 34956 KB Output is correct
50 Correct 147 ms 34824 KB Output is correct
51 Correct 142 ms 34888 KB Output is correct
52 Correct 151 ms 34952 KB Output is correct
53 Correct 148 ms 34940 KB Output is correct
54 Correct 157 ms 35636 KB Output is correct
55 Correct 124 ms 33272 KB Output is correct
56 Correct 165 ms 34092 KB Output is correct
57 Correct 1216 ms 91400 KB Output is correct
58 Correct 1220 ms 91396 KB Output is correct
59 Correct 1115 ms 92208 KB Output is correct
60 Correct 1194 ms 92244 KB Output is correct
61 Correct 1142 ms 92564 KB Output is correct
62 Correct 1157 ms 92152 KB Output is correct
63 Correct 809 ms 77580 KB Output is correct
64 Correct 753 ms 77572 KB Output is correct
65 Correct 991 ms 75816 KB Output is correct
66 Correct 1016 ms 75784 KB Output is correct
67 Correct 989 ms 75956 KB Output is correct
68 Correct 1012 ms 74612 KB Output is correct
69 Correct 1010 ms 74692 KB Output is correct
70 Correct 1025 ms 74876 KB Output is correct
71 Correct 1047 ms 75020 KB Output is correct
72 Correct 1018 ms 74844 KB Output is correct
73 Correct 697 ms 72844 KB Output is correct
74 Correct 732 ms 72780 KB Output is correct
75 Correct 685 ms 72656 KB Output is correct
76 Correct 671 ms 73128 KB Output is correct
77 Correct 685 ms 72748 KB Output is correct
78 Correct 904 ms 77408 KB Output is correct
79 Correct 662 ms 65764 KB Output is correct
80 Correct 855 ms 70900 KB Output is correct