oj.uz

Submission #539187

# Submission time Handle Problem Language Result Execution time Memory
539187 2022-03-18T14:40:47 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 205944 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef complex<double> cd; // !!! long double slow

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


int n, q;
const int INF = 1000 * 1000 * 1000 + 10;
const int MX = 2 * 1000 * 1000;
int ol[MX];


bool cmp(int v1, int v2) {
	return ol[v1] < ol[v2];
}


struct Seg {
	int mx[MX], t[MX];
	vi sl[MX];

	Seg(vi& a) {
		for(int p = n; p < 2 * n; p++) {
			mx[p] = a[p - n];
			sl[p].reserve(1);
			sl[p].pb(a[p - n]);
			t[p] = -INF;
			ol[p] = p - n;
		}

		for(int p = n - 1; p > 0; p--) {
			ol[p] = min(ol[2 * p], ol[2 * p + 1]);
			mx[p] = max(mx[2 * p], mx[2 * p + 1]);
			t[p] = max(t[2 * p], t[2 * p + 1]);
			sl[p].reserve(sz(sl[2 * p]) + sz(sl[2 * p + 1]));
			merge(all(sl[2 * p]), all(sl[2 * p + 1]), back_inserter(sl[p]));

			int ind = lower_bound(all(sl[2 * p + 1]), mx[2 * p]) - sl[2 * p + 1].begin();
			if(ind != 0)
				maxeq(t[p], mx[2 * p] + sl[2 * p + 1][ind - 1]);
		}
	}

	bool query(int l, int r, int k, int left_max) {
		vi vert;
		for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) {
				int v = l++;
				if(t[v] > k)
					return false;
				vert.pb(v);
			}
			if (r & 1) {
				int v = --r;
				if(t[v] > k)
					return false;
				vert.pb(v);
			}
		}
		sort(all(vert), cmp);

		for(int v: vert) {
			int ind = lower_bound(all(sl[v]), left_max) - sl[v].begin();
			if(ind != 0 && left_max + sl[v][ind - 1] > k)
				return false;

			maxeq(left_max, mx[v]);
		}

		return true;
	}
};



void solve() {
	cin >> n >> q;
	vi a(n);
	forn(i, n)
		cin >> a[i];

	Seg seg(a);

	forn(_, q) {
		int l, r, k;
		cin >> l >> r >> k;
		l--; r--;

		auto ans = seg.query(l, r, k, -INF);
		cout << ans << '\n';
	}
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

//	freopen("boards.in", "r", stdin);
//	freopen("boards.out", "w", stdout);

    int t = 1;
//  cin >> t;
    while(t--) {
        solve();
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62796 KB Output is correct
2 Correct 37 ms 62916 KB Output is correct
3 Correct 44 ms 62948 KB Output is correct
4 Correct 45 ms 62896 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct
6 Correct 41 ms 62916 KB Output is correct
7 Correct 40 ms 62928 KB Output is correct
8 Correct 39 ms 62948 KB Output is correct
9 Correct 43 ms 62856 KB Output is correct
10 Correct 43 ms 62940 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62796 KB Output is correct
2 Correct 37 ms 62916 KB Output is correct
3 Correct 44 ms 62948 KB Output is correct
4 Correct 45 ms 62896 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct
6 Correct 41 ms 62916 KB Output is correct
7 Correct 40 ms 62928 KB Output is correct
8 Correct 39 ms 62948 KB Output is correct
9 Correct 43 ms 62856 KB Output is correct
10 Correct 43 ms 62940 KB Output is correct
11 Correct 46 ms 63048 KB Output is correct
12 Correct 52 ms 63460 KB Output is correct
13 Correct 55 ms 63464 KB Output is correct
14 Correct 42 ms 63432 KB Output is correct
15 Correct 42 ms 63472 KB Output is correct
16 Correct 43 ms 63468 KB Output is correct
17 Correct 41 ms 63324 KB Output is correct
18 Correct 51 ms 63464 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 205924 KB Output is correct
2 Correct 1107 ms 205872 KB Output is correct
3 Correct 1092 ms 205944 KB Output is correct
4 Correct 1068 ms 205760 KB Output is correct
5 Execution timed out 3018 ms 204960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 75948 KB Output is correct
2 Correct 163 ms 75944 KB Output is correct
3 Correct 251 ms 75876 KB Output is correct
4 Correct 304 ms 75972 KB Output is correct
5 Correct 269 ms 76052 KB Output is correct
6 Correct 121 ms 75852 KB Output is correct
7 Correct 125 ms 75944 KB Output is correct
8 Correct 190 ms 75820 KB Output is correct
9 Correct 111 ms 63164 KB Output is correct
10 Correct 163 ms 75944 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62796 KB Output is correct
2 Correct 37 ms 62916 KB Output is correct
3 Correct 44 ms 62948 KB Output is correct
4 Correct 45 ms 62896 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct
6 Correct 41 ms 62916 KB Output is correct
7 Correct 40 ms 62928 KB Output is correct
8 Correct 39 ms 62948 KB Output is correct
9 Correct 43 ms 62856 KB Output is correct
10 Correct 43 ms 62940 KB Output is correct
11 Correct 46 ms 63048 KB Output is correct
12 Correct 52 ms 63460 KB Output is correct
13 Correct 55 ms 63464 KB Output is correct
14 Correct 42 ms 63432 KB Output is correct
15 Correct 42 ms 63472 KB Output is correct
16 Correct 43 ms 63468 KB Output is correct
17 Correct 41 ms 63324 KB Output is correct
18 Correct 51 ms 63464 KB Output is correct
19 Correct 387 ms 89644 KB Output is correct
20 Correct 368 ms 89660 KB Output is correct
21 Correct 312 ms 89728 KB Output is correct
22 Correct 326 ms 89700 KB Output is correct
23 Correct 345 ms 89752 KB Output is correct
24 Correct 630 ms 89720 KB Output is correct
25 Correct 532 ms 89740 KB Output is correct
26 Correct 1150 ms 89664 KB Output is correct
27 Correct 893 ms 90200 KB Output is correct
28 Correct 893 ms 90240 KB Output is correct
29 Correct 866 ms 90176 KB Output is correct
30 Correct 939 ms 90200 KB Output is correct
31 Correct 889 ms 90216 KB Output is correct
32 Correct 790 ms 90244 KB Output is correct
33 Correct 784 ms 90192 KB Output is correct
34 Correct 354 ms 90248 KB Output is correct
35 Correct 342 ms 90228 KB Output is correct
36 Correct 379 ms 90180 KB Output is correct
37 Correct 373 ms 90252 KB Output is correct
38 Correct 396 ms 90336 KB Output is correct
39 Correct 399 ms 90188 KB Output is correct
40 Correct 389 ms 80788 KB Output is correct
41 Correct 404 ms 90212 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62796 KB Output is correct
2 Correct 37 ms 62916 KB Output is correct
3 Correct 44 ms 62948 KB Output is correct
4 Correct 45 ms 62896 KB Output is correct
5 Correct 36 ms 62936 KB Output is correct
6 Correct 41 ms 62916 KB Output is correct
7 Correct 40 ms 62928 KB Output is correct
8 Correct 39 ms 62948 KB Output is correct
9 Correct 43 ms 62856 KB Output is correct
10 Correct 43 ms 62940 KB Output is correct
11 Correct 46 ms 63048 KB Output is correct
12 Correct 52 ms 63460 KB Output is correct
13 Correct 55 ms 63464 KB Output is correct
14 Correct 42 ms 63432 KB Output is correct
15 Correct 42 ms 63472 KB Output is correct
16 Correct 43 ms 63468 KB Output is correct
17 Correct 41 ms 63324 KB Output is correct
18 Correct 51 ms 63464 KB Output is correct
19 Correct 1128 ms 205924 KB Output is correct
20 Correct 1107 ms 205872 KB Output is correct
21 Correct 1092 ms 205944 KB Output is correct
22 Correct 1068 ms 205760 KB Output is correct
23 Execution timed out 3018 ms 204960 KB Time limit exceeded
24 Halted 0 ms 0 KB -