oj.uz

Submission #541356

# Submission time Handle Problem Language Result Execution time Memory
541356 2022-03-23T08:14:00 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 823 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) {
				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 65 ms 133488 KB Output is correct
2 Correct 64 ms 133516 KB Output is correct
3 Correct 65 ms 133548 KB Output is correct
4 Correct 65 ms 133464 KB Output is correct
5 Correct 64 ms 133492 KB Output is correct
6 Correct 65 ms 133564 KB Output is correct
7 Correct 65 ms 133580 KB Output is correct
8 Correct 68 ms 133592 KB Output is correct
9 Correct 68 ms 133540 KB Output is correct
10 Correct 69 ms 133464 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 133488 KB Output is correct
2 Correct 64 ms 133516 KB Output is correct
3 Correct 65 ms 133548 KB Output is correct
4 Correct 65 ms 133464 KB Output is correct
5 Correct 64 ms 133492 KB Output is correct
6 Correct 65 ms 133564 KB Output is correct
7 Correct 65 ms 133580 KB Output is correct
8 Correct 68 ms 133592 KB Output is correct
9 Correct 68 ms 133540 KB Output is correct
10 Correct 69 ms 133464 KB Output is correct
11 Correct 69 ms 133964 KB Output is correct
12 Correct 72 ms 134164 KB Output is correct
13 Correct 72 ms 134232 KB Output is correct
14 Correct 74 ms 134208 KB Output is correct
15 Correct 74 ms 134272 KB Output is correct
16 Correct 77 ms 134260 KB Output is correct
17 Correct 76 ms 134140 KB Output is correct
18 Correct 73 ms 134224 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 608 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 301 ms 147484 KB Output is correct
3 Correct 325 ms 147484 KB Output is correct
4 Correct 319 ms 147440 KB Output is correct
5 Correct 314 ms 147392 KB Output is correct
6 Correct 249 ms 147504 KB Output is correct
7 Correct 261 ms 147396 KB Output is correct
8 Correct 267 ms 147432 KB Output is correct
9 Correct 116 ms 135056 KB Output is correct
10 Correct 263 ms 147424 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 133488 KB Output is correct
2 Correct 64 ms 133516 KB Output is correct
3 Correct 65 ms 133548 KB Output is correct
4 Correct 65 ms 133464 KB Output is correct
5 Correct 64 ms 133492 KB Output is correct
6 Correct 65 ms 133564 KB Output is correct
7 Correct 65 ms 133580 KB Output is correct
8 Correct 68 ms 133592 KB Output is correct
9 Correct 68 ms 133540 KB Output is correct
10 Correct 69 ms 133464 KB Output is correct
11 Correct 69 ms 133964 KB Output is correct
12 Correct 72 ms 134164 KB Output is correct
13 Correct 72 ms 134232 KB Output is correct
14 Correct 74 ms 134208 KB Output is correct
15 Correct 74 ms 134272 KB Output is correct
16 Correct 77 ms 134260 KB Output is correct
17 Correct 76 ms 134140 KB Output is correct
18 Correct 73 ms 134224 KB Output is correct
19 Correct 652 ms 162204 KB Output is correct
20 Correct 640 ms 162192 KB Output is correct
21 Correct 602 ms 162300 KB Output is correct
22 Correct 611 ms 162168 KB Output is correct
23 Correct 624 ms 162260 KB Output is correct
24 Correct 578 ms 162220 KB Output is correct
25 Correct 572 ms 162248 KB Output is correct
26 Correct 717 ms 162240 KB Output is correct
27 Correct 756 ms 162228 KB Output is correct
28 Correct 777 ms 162184 KB Output is correct
29 Correct 823 ms 162228 KB Output is correct
30 Correct 755 ms 162240 KB Output is correct
31 Correct 763 ms 162168 KB Output is correct
32 Correct 799 ms 162148 KB Output is correct
33 Correct 779 ms 162252 KB Output is correct
34 Correct 523 ms 162240 KB Output is correct
35 Correct 516 ms 162140 KB Output is correct
36 Correct 518 ms 162188 KB Output is correct
37 Correct 514 ms 162240 KB Output is correct
38 Correct 517 ms 162228 KB Output is correct
39 Correct 626 ms 162168 KB Output is correct
40 Correct 455 ms 152044 KB Output is correct
41 Correct 492 ms 162232 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 133488 KB Output is correct
2 Correct 64 ms 133516 KB Output is correct
3 Correct 65 ms 133548 KB Output is correct
4 Correct 65 ms 133464 KB Output is correct
5 Correct 64 ms 133492 KB Output is correct
6 Correct 65 ms 133564 KB Output is correct
7 Correct 65 ms 133580 KB Output is correct
8 Correct 68 ms 133592 KB Output is correct
9 Correct 68 ms 133540 KB Output is correct
10 Correct 69 ms 133464 KB Output is correct
11 Correct 69 ms 133964 KB Output is correct
12 Correct 72 ms 134164 KB Output is correct
13 Correct 72 ms 134232 KB Output is correct
14 Correct 74 ms 134208 KB Output is correct
15 Correct 74 ms 134272 KB Output is correct
16 Correct 77 ms 134260 KB Output is correct
17 Correct 76 ms 134140 KB Output is correct
18 Correct 73 ms 134224 KB Output is correct
19 Runtime error 608 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -