oj.uz

Submission #541357

# Submission time Handle Problem Language Result Execution time Memory
541357 2022-03-23T08:15:06 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 775 ms 262144 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 MXd2 = 1000 * 1000;
const int MX = 2 * MXd2;
int ol[MX], oright[MX];
vector<bool> ans(MXd2, true);
vii mx2vq[MXd2];
vii v2mxq[MX];
int Ks[MX];
vi vals;
vi a;


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


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

	Seg() {
		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] = -1;
			oright[p] = ol[p] = p - n;
		}

		for(int p = n - 1; p > 0; p--) {
			ol[p] = min(ol[2 * p], ol[2 * p + 1]);
			oright[p] = max(oright[2 * p], oright[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], vals[mx[2 * p]] + vals[sl[2 * p + 1][ind - 1]]);
		}

		forn(p, 2 * n)
			vi().swap(sl[p]);
	}

	void query(int l, int r, int k, int left_max, int q) {
		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);

		for(int v: vert) {
			if(t[v] > k) {
				ans[q] = false;
				return;
			}

			if(left_max != -1) {
				mx2vq[left_max].eb(v, q);
			}

			maxeq(left_max, mx[v]);
		}
	}


	void process() {
		for(int lm = sz(vals) - 1; lm >= 0; --lm) {
			if(lm != sz(vals) - 1)
				vii().swap(mx2vq[lm + 1]);
			for(ii p: mx2vq[lm]) {
				if(ans[p.S])
					v2mxq[p.F].eb(lm, p.S);
			}
		}
		vii().swap(mx2vq[0]);

		for(int p = 2 * n - 1; p > 0; p--) {
			if(p < n) {
				if(sz(sl[p]))
					vi().swap(sl[p]);
				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]));
				vi().swap(sl[2 * p]);
				vi().swap(sl[2 * p + 1]);
			}
			else {
				sl[p].reserve(1);
				sl[p].pb(a[p - n]);
			}

			int x = sz(sl[p]) - 1;
			forn(w, sz(v2mxq[p])) {
				int lm = v2mxq[p][w].F, q = v2mxq[p][w].S;
				int k = Ks[q];
				if(!ans[q])
					continue;

				while(x >= 0 && sl[p][x] >= lm)
					x--;

				if(x < 0)
					break;

				if(vals[sl[p][x]] >= k - vals[lm] + 1) {
					ans[q] = false;
				}
			}

			vii().swap(v2mxq[p]);
		}
	}
};


int v2c(int v) {
	return lower_bound(all(vals), v) - vals.begin();
}


void solve() {
	cin >> n >> Q;
	a.resize(n);
	forn(i, n) {
		cin >> a[i];
		vals.pb(a[i]);
	}
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());

	forn(i, n)
		a[i] = v2c(a[i]);

	Seg seg;

	int QQ = Q / 4;
	forn(q, Q) {
		int l, r, k;
		cin >> l >> r >> k;
		l--; r--;
		Ks[q] = k;

		seg.query(l, r, k, -1, q);

		if(q == QQ || q == 2 * QQ || q == 3 * QQ)
			seg.process();
	}

	seg.process();
	forn(i, Q) {
		cout << ans[i] << '\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 64 ms 133516 KB Output is correct
2 Correct 65 ms 133432 KB Output is correct
3 Correct 68 ms 133488 KB Output is correct
4 Correct 67 ms 133428 KB Output is correct
5 Correct 64 ms 133508 KB Output is correct
6 Correct 64 ms 133564 KB Output is correct
7 Correct 66 ms 133516 KB Output is correct
8 Correct 66 ms 133560 KB Output is correct
9 Correct 69 ms 133456 KB Output is correct
10 Correct 71 ms 133536 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133516 KB Output is correct
2 Correct 65 ms 133432 KB Output is correct
3 Correct 68 ms 133488 KB Output is correct
4 Correct 67 ms 133428 KB Output is correct
5 Correct 64 ms 133508 KB Output is correct
6 Correct 64 ms 133564 KB Output is correct
7 Correct 66 ms 133516 KB Output is correct
8 Correct 66 ms 133560 KB Output is correct
9 Correct 69 ms 133456 KB Output is correct
10 Correct 71 ms 133536 KB Output is correct
11 Correct 69 ms 133608 KB Output is correct
12 Correct 72 ms 134128 KB Output is correct
13 Correct 72 ms 134120 KB Output is correct
14 Correct 74 ms 134148 KB Output is correct
15 Correct 75 ms 134172 KB Output is correct
16 Correct 75 ms 134096 KB Output is correct
17 Correct 74 ms 134032 KB Output is correct
18 Correct 74 ms 134136 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 147496 KB Output is correct
2 Correct 298 ms 147408 KB Output is correct
3 Correct 320 ms 147436 KB Output is correct
4 Correct 335 ms 147464 KB Output is correct
5 Correct 326 ms 147468 KB Output is correct
6 Correct 248 ms 147396 KB Output is correct
7 Correct 242 ms 147488 KB Output is correct
8 Correct 274 ms 147504 KB Output is correct
9 Correct 118 ms 134864 KB Output is correct
10 Correct 251 ms 147412 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133516 KB Output is correct
2 Correct 65 ms 133432 KB Output is correct
3 Correct 68 ms 133488 KB Output is correct
4 Correct 67 ms 133428 KB Output is correct
5 Correct 64 ms 133508 KB Output is correct
6 Correct 64 ms 133564 KB Output is correct
7 Correct 66 ms 133516 KB Output is correct
8 Correct 66 ms 133560 KB Output is correct
9 Correct 69 ms 133456 KB Output is correct
10 Correct 71 ms 133536 KB Output is correct
11 Correct 69 ms 133608 KB Output is correct
12 Correct 72 ms 134128 KB Output is correct
13 Correct 72 ms 134120 KB Output is correct
14 Correct 74 ms 134148 KB Output is correct
15 Correct 75 ms 134172 KB Output is correct
16 Correct 75 ms 134096 KB Output is correct
17 Correct 74 ms 134032 KB Output is correct
18 Correct 74 ms 134136 KB Output is correct
19 Correct 662 ms 162240 KB Output is correct
20 Correct 638 ms 162212 KB Output is correct
21 Correct 628 ms 162152 KB Output is correct
22 Correct 610 ms 162192 KB Output is correct
23 Correct 620 ms 162240 KB Output is correct
24 Correct 568 ms 162224 KB Output is correct
25 Correct 567 ms 162196 KB Output is correct
26 Correct 718 ms 162152 KB Output is correct
27 Correct 707 ms 162204 KB Output is correct
28 Correct 756 ms 162204 KB Output is correct
29 Correct 758 ms 162192 KB Output is correct
30 Correct 763 ms 162160 KB Output is correct
31 Correct 775 ms 162232 KB Output is correct
32 Correct 770 ms 162192 KB Output is correct
33 Correct 775 ms 162164 KB Output is correct
34 Correct 511 ms 162236 KB Output is correct
35 Correct 521 ms 162240 KB Output is correct
36 Correct 505 ms 162156 KB Output is correct
37 Correct 505 ms 162236 KB Output is correct
38 Correct 515 ms 162184 KB Output is correct
39 Correct 629 ms 162144 KB Output is correct
40 Correct 446 ms 151936 KB Output is correct
41 Correct 498 ms 162224 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133516 KB Output is correct
2 Correct 65 ms 133432 KB Output is correct
3 Correct 68 ms 133488 KB Output is correct
4 Correct 67 ms 133428 KB Output is correct
5 Correct 64 ms 133508 KB Output is correct
6 Correct 64 ms 133564 KB Output is correct
7 Correct 66 ms 133516 KB Output is correct
8 Correct 66 ms 133560 KB Output is correct
9 Correct 69 ms 133456 KB Output is correct
10 Correct 71 ms 133536 KB Output is correct
11 Correct 69 ms 133608 KB Output is correct
12 Correct 72 ms 134128 KB Output is correct
13 Correct 72 ms 134120 KB Output is correct
14 Correct 74 ms 134148 KB Output is correct
15 Correct 75 ms 134172 KB Output is correct
16 Correct 75 ms 134096 KB Output is correct
17 Correct 74 ms 134032 KB Output is correct
18 Correct 74 ms 134136 KB Output is correct
19 Runtime error 628 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -