oj.uz

Submission #541351

# Submission time Handle Problem Language Result Execution time Memory
541351 2022-03-23T08:03:58 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 377 ms 43740 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 = 100 * 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].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]);
			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]]);
		}

		forbn(p, 1, 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);
			}
		}

		for(int p = 2 * n - 1; p > 0; p--) {
			if(p < n) {
				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]);
			}

			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;
				}
			}
		}
	}
};


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;

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

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

	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 7 ms 13652 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 8 ms 13652 KB Output is correct
5 Correct 8 ms 13652 KB Output is correct
6 Correct 8 ms 13664 KB Output is correct
7 Correct 8 ms 13668 KB Output is correct
8 Correct 8 ms 13608 KB Output is correct
9 Correct 8 ms 13652 KB Output is correct
10 Correct 8 ms 13652 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 8 ms 13652 KB Output is correct
5 Correct 8 ms 13652 KB Output is correct
6 Correct 8 ms 13664 KB Output is correct
7 Correct 8 ms 13668 KB Output is correct
8 Correct 8 ms 13608 KB Output is correct
9 Correct 8 ms 13652 KB Output is correct
10 Correct 8 ms 13652 KB Output is correct
11 Correct 10 ms 13908 KB Output is correct
12 Correct 14 ms 14412 KB Output is correct
13 Correct 13 ms 14304 KB Output is correct
14 Correct 15 ms 14464 KB Output is correct
15 Correct 14 ms 14432 KB Output is correct
16 Correct 15 ms 14416 KB Output is correct
17 Correct 13 ms 14296 KB Output is correct
18 Correct 14 ms 14548 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 377 ms 43740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 28040 KB Output is correct
2 Correct 196 ms 28132 KB Output is correct
3 Correct 227 ms 37184 KB Output is correct
4 Correct 211 ms 36756 KB Output is correct
5 Correct 204 ms 35284 KB Output is correct
6 Correct 154 ms 29136 KB Output is correct
7 Correct 156 ms 29272 KB Output is correct
8 Correct 174 ms 34264 KB Output is correct
9 Correct 58 ms 18760 KB Output is correct
10 Correct 177 ms 35140 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 8 ms 13652 KB Output is correct
5 Correct 8 ms 13652 KB Output is correct
6 Correct 8 ms 13664 KB Output is correct
7 Correct 8 ms 13668 KB Output is correct
8 Correct 8 ms 13608 KB Output is correct
9 Correct 8 ms 13652 KB Output is correct
10 Correct 8 ms 13652 KB Output is correct
11 Correct 10 ms 13908 KB Output is correct
12 Correct 14 ms 14412 KB Output is correct
13 Correct 13 ms 14304 KB Output is correct
14 Correct 15 ms 14464 KB Output is correct
15 Correct 14 ms 14432 KB Output is correct
16 Correct 15 ms 14416 KB Output is correct
17 Correct 13 ms 14296 KB Output is correct
18 Correct 14 ms 14548 KB Output is correct
19 Runtime error 83 ms 31544 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 13524 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Correct 8 ms 13652 KB Output is correct
5 Correct 8 ms 13652 KB Output is correct
6 Correct 8 ms 13664 KB Output is correct
7 Correct 8 ms 13668 KB Output is correct
8 Correct 8 ms 13608 KB Output is correct
9 Correct 8 ms 13652 KB Output is correct
10 Correct 8 ms 13652 KB Output is correct
11 Correct 10 ms 13908 KB Output is correct
12 Correct 14 ms 14412 KB Output is correct
13 Correct 13 ms 14304 KB Output is correct
14 Correct 15 ms 14464 KB Output is correct
15 Correct 14 ms 14432 KB Output is correct
16 Correct 15 ms 14416 KB Output is correct
17 Correct 13 ms 14296 KB Output is correct
18 Correct 14 ms 14548 KB Output is correct
19 Runtime error 377 ms 43740 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -