oj.uz

Submission #541336

# Submission time Handle Problem Language Result Execution time Memory
541336 2022-03-23T06:48:56 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 215240 KB 
#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];
	int* sl[MX];
	int razmer[MX];

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

			razmer[p] = 1;
			sl[p] = new int[razmer[p]];
			sl[p][0] = a[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]);

			razmer[p] = razmer[2 * p] + razmer[2 * p + 1];
			sl[p] = new int[razmer[p]];
			merge(sl[2 * p], sl[2 * p] + razmer[2 * p], sl[2 * p + 1], sl[2 * p + 1] + razmer[2 * p + 1], sl[p]);

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

//		forbn(p, 1, 2 * n) {
//			delete sl[p];
//		}
	}

	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) {
				vert.pb(l++);
			}
			if (r & 1) {
				vert.pb(--r);
			}
		}
		sort(all(vert), cmp);

		bool ans = true;
		for(int v: vert) {
			ans = ans && t[v] <= k;
			int rp = left_max - 1, lp = k - left_max + 1;

			if(lp <= rp) {
				int indl = lower_bound(sl[v], sl[v] + razmer[v], lp) - sl[v];
				int indr = lower_bound(sl[v], sl[v] + razmer[v], rp + 1) - sl[v];

				ans = ans && indl == indr;
			}

			if(!ans)
				return ans;

			maxeq(left_max, mx[v]);
		}

		return ans;
	}
};



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 16 ms 39384 KB Output is correct
2 Correct 17 ms 39428 KB Output is correct
3 Correct 17 ms 39464 KB Output is correct
4 Correct 16 ms 39380 KB Output is correct
5 Correct 17 ms 39464 KB Output is correct
6 Correct 17 ms 39444 KB Output is correct
7 Correct 16 ms 39508 KB Output is correct
8 Correct 16 ms 39508 KB Output is correct
9 Correct 18 ms 39380 KB Output is correct
10 Correct 16 ms 39464 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39384 KB Output is correct
2 Correct 17 ms 39428 KB Output is correct
3 Correct 17 ms 39464 KB Output is correct
4 Correct 16 ms 39380 KB Output is correct
5 Correct 17 ms 39464 KB Output is correct
6 Correct 17 ms 39444 KB Output is correct
7 Correct 16 ms 39508 KB Output is correct
8 Correct 16 ms 39508 KB Output is correct
9 Correct 18 ms 39380 KB Output is correct
10 Correct 16 ms 39464 KB Output is correct
11 Correct 18 ms 39628 KB Output is correct
12 Correct 19 ms 40088 KB Output is correct
13 Correct 19 ms 40020 KB Output is correct
14 Correct 20 ms 40172 KB Output is correct
15 Correct 22 ms 40116 KB Output is correct
16 Correct 25 ms 40020 KB Output is correct
17 Correct 21 ms 40004 KB Output is correct
18 Correct 21 ms 39988 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1832 ms 214216 KB Output is correct
2 Correct 1887 ms 215196 KB Output is correct
3 Correct 1893 ms 215116 KB Output is correct
4 Correct 1864 ms 215240 KB Output is correct
5 Execution timed out 3090 ms 207980 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 53968 KB Output is correct
2 Correct 148 ms 54452 KB Output is correct
3 Correct 229 ms 54328 KB Output is correct
4 Correct 183 ms 54440 KB Output is correct
5 Correct 182 ms 54348 KB Output is correct
6 Correct 135 ms 54176 KB Output is correct
7 Correct 131 ms 54280 KB Output is correct
8 Correct 124 ms 54052 KB Output is correct
9 Correct 66 ms 40896 KB Output is correct
10 Correct 121 ms 54032 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39384 KB Output is correct
2 Correct 17 ms 39428 KB Output is correct
3 Correct 17 ms 39464 KB Output is correct
4 Correct 16 ms 39380 KB Output is correct
5 Correct 17 ms 39464 KB Output is correct
6 Correct 17 ms 39444 KB Output is correct
7 Correct 16 ms 39508 KB Output is correct
8 Correct 16 ms 39508 KB Output is correct
9 Correct 18 ms 39380 KB Output is correct
10 Correct 16 ms 39464 KB Output is correct
11 Correct 18 ms 39628 KB Output is correct
12 Correct 19 ms 40088 KB Output is correct
13 Correct 19 ms 40020 KB Output is correct
14 Correct 20 ms 40172 KB Output is correct
15 Correct 22 ms 40116 KB Output is correct
16 Correct 25 ms 40020 KB Output is correct
17 Correct 21 ms 40004 KB Output is correct
18 Correct 21 ms 39988 KB Output is correct
19 Correct 342 ms 72856 KB Output is correct
20 Correct 364 ms 72828 KB Output is correct
21 Correct 319 ms 72696 KB Output is correct
22 Correct 323 ms 72660 KB Output is correct
23 Correct 308 ms 72672 KB Output is correct
24 Correct 347 ms 72556 KB Output is correct
25 Correct 325 ms 72512 KB Output is correct
26 Correct 435 ms 72744 KB Output is correct
27 Correct 435 ms 72780 KB Output is correct
28 Correct 497 ms 72776 KB Output is correct
29 Correct 457 ms 72928 KB Output is correct
30 Correct 525 ms 72740 KB Output is correct
31 Correct 462 ms 72864 KB Output is correct
32 Correct 482 ms 72912 KB Output is correct
33 Correct 502 ms 72944 KB Output is correct
34 Correct 305 ms 72508 KB Output is correct
35 Correct 303 ms 72428 KB Output is correct
36 Correct 290 ms 72268 KB Output is correct
37 Correct 290 ms 72192 KB Output is correct
38 Correct 321 ms 72476 KB Output is correct
39 Correct 281 ms 71328 KB Output is correct
40 Correct 177 ms 61284 KB Output is correct
41 Correct 260 ms 70988 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39384 KB Output is correct
2 Correct 17 ms 39428 KB Output is correct
3 Correct 17 ms 39464 KB Output is correct
4 Correct 16 ms 39380 KB Output is correct
5 Correct 17 ms 39464 KB Output is correct
6 Correct 17 ms 39444 KB Output is correct
7 Correct 16 ms 39508 KB Output is correct
8 Correct 16 ms 39508 KB Output is correct
9 Correct 18 ms 39380 KB Output is correct
10 Correct 16 ms 39464 KB Output is correct
11 Correct 18 ms 39628 KB Output is correct
12 Correct 19 ms 40088 KB Output is correct
13 Correct 19 ms 40020 KB Output is correct
14 Correct 20 ms 40172 KB Output is correct
15 Correct 22 ms 40116 KB Output is correct
16 Correct 25 ms 40020 KB Output is correct
17 Correct 21 ms 40004 KB Output is correct
18 Correct 21 ms 39988 KB Output is correct
19 Correct 1832 ms 214216 KB Output is correct
20 Correct 1887 ms 215196 KB Output is correct
21 Correct 1893 ms 215116 KB Output is correct
22 Correct 1864 ms 215240 KB Output is correct
23 Execution timed out 3090 ms 207980 KB Time limit exceeded
24 Halted 0 ms 0 KB -