oj.uz

Submission #539122

# Submission time Handle Problem Language Result Execution time Memory
539122 2022-03-18T12:42:24 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1257 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 INF = 1000 * 1000 * 1000 + 10;
const int MX = 2 * 1000 * 1000;
int ol[MX], oright[MX];
bool res[MX];
vi a;


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


struct Seg {
	int mx[MX], t[MX];
	vi sl[MX];
	vector<ii> rem[MX];

	Seg(vi& a) {
		forn(i, MX)
			res[i] = true;
		for(int p = n; p < 2 * n; p++) {
			mx[p] = a[p - n];
			sl[p].pb(a[p - n]);
			t[p] = -INF;
			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], mx[2 * p] + sl[2 * p + 1][ind - 1]);
		}

		forn(i, MX)
			sl[i].clear();
	}

	void query(int l, int r, int k, int left_max, int qid) {
		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) {
				rem[v].pb({lp - 1, qid});
				rem[v].pb({rp, qid});
			}

			maxeq(left_max, mx[v]);
		}

		res[qid] = ans;
	}

	void process() {
		for(int v = 1; v < 2 * n; v++) {
			sort(all(rem[v]));
			vi slv;
			for(int j = ol[v]; j <= oright[v]; j++)
				slv.pb(a[j]);
			sort(all(slv));

			set<int> act;
			int i = 0;

			for(ii p: rem[v]) {
				int qid = p.S;
				if(res[qid] == false)
					continue;
				int en = p.F;

				if(i < sz(slv) && slv[i] <= en) {
					for(int qid_act: act) {
						res[qid_act] = false;
					}
					act.clear();
				}
				while(i < sz(slv) && slv[i] <= en)
					i += 1;

				if(act.find(qid) == act.end()) {
					act.insert(qid);
				}
				else {
					act.erase(qid);
				}
			}
		}
	}
};



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

	Seg seg(a);

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

		seg.query(l, r, k, -INF, qid);
	}

	seg.process();

	forn(qid, q) {
		cout << res[qid] << '\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 71 ms 111776 KB Output is correct
2 Correct 68 ms 111820 KB Output is correct
3 Correct 74 ms 111856 KB Output is correct
4 Correct 67 ms 111820 KB Output is correct
5 Correct 67 ms 111828 KB Output is correct
6 Correct 69 ms 111876 KB Output is correct
7 Correct 69 ms 111888 KB Output is correct
8 Correct 73 ms 111952 KB Output is correct
9 Correct 69 ms 111876 KB Output is correct
10 Correct 69 ms 111944 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111776 KB Output is correct
2 Correct 68 ms 111820 KB Output is correct
3 Correct 74 ms 111856 KB Output is correct
4 Correct 67 ms 111820 KB Output is correct
5 Correct 67 ms 111828 KB Output is correct
6 Correct 69 ms 111876 KB Output is correct
7 Correct 69 ms 111888 KB Output is correct
8 Correct 73 ms 111952 KB Output is correct
9 Correct 69 ms 111876 KB Output is correct
10 Correct 69 ms 111944 KB Output is correct
11 Correct 74 ms 112428 KB Output is correct
12 Correct 84 ms 113144 KB Output is correct
13 Correct 83 ms 113052 KB Output is correct
14 Correct 90 ms 113516 KB Output is correct
15 Correct 89 ms 113452 KB Output is correct
16 Correct 82 ms 112872 KB Output is correct
17 Correct 73 ms 112364 KB Output is correct
18 Correct 78 ms 112952 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 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 513 ms 147036 KB Output is correct
2 Correct 533 ms 149028 KB Output is correct
3 Correct 509 ms 141064 KB Output is correct
4 Correct 467 ms 140764 KB Output is correct
5 Correct 459 ms 140220 KB Output is correct
6 Correct 337 ms 138152 KB Output is correct
7 Correct 328 ms 138224 KB Output is correct
8 Correct 343 ms 138668 KB Output is correct
9 Correct 125 ms 112120 KB Output is correct
10 Correct 296 ms 137408 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111776 KB Output is correct
2 Correct 68 ms 111820 KB Output is correct
3 Correct 74 ms 111856 KB Output is correct
4 Correct 67 ms 111820 KB Output is correct
5 Correct 67 ms 111828 KB Output is correct
6 Correct 69 ms 111876 KB Output is correct
7 Correct 69 ms 111888 KB Output is correct
8 Correct 73 ms 111952 KB Output is correct
9 Correct 69 ms 111876 KB Output is correct
10 Correct 69 ms 111944 KB Output is correct
11 Correct 74 ms 112428 KB Output is correct
12 Correct 84 ms 113144 KB Output is correct
13 Correct 83 ms 113052 KB Output is correct
14 Correct 90 ms 113516 KB Output is correct
15 Correct 89 ms 113452 KB Output is correct
16 Correct 82 ms 112872 KB Output is correct
17 Correct 73 ms 112364 KB Output is correct
18 Correct 78 ms 112952 KB Output is correct
19 Correct 1201 ms 188404 KB Output is correct
20 Correct 1207 ms 188312 KB Output is correct
21 Correct 1128 ms 190536 KB Output is correct
22 Correct 1134 ms 190984 KB Output is correct
23 Correct 1180 ms 191100 KB Output is correct
24 Correct 964 ms 169824 KB Output is correct
25 Correct 977 ms 169388 KB Output is correct
26 Correct 1144 ms 174244 KB Output is correct
27 Correct 1257 ms 174172 KB Output is correct
28 Correct 1203 ms 175308 KB Output is correct
29 Correct 1145 ms 173996 KB Output is correct
30 Correct 1054 ms 173816 KB Output is correct
31 Correct 1039 ms 175156 KB Output is correct
32 Correct 1061 ms 174924 KB Output is correct
33 Correct 1036 ms 175048 KB Output is correct
34 Correct 819 ms 169616 KB Output is correct
35 Correct 809 ms 169632 KB Output is correct
36 Correct 796 ms 169532 KB Output is correct
37 Correct 806 ms 169480 KB Output is correct
38 Correct 825 ms 169636 KB Output is correct
39 Correct 725 ms 163380 KB Output is correct
40 Correct 313 ms 130816 KB Output is correct
41 Correct 575 ms 164564 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111776 KB Output is correct
2 Correct 68 ms 111820 KB Output is correct
3 Correct 74 ms 111856 KB Output is correct
4 Correct 67 ms 111820 KB Output is correct
5 Correct 67 ms 111828 KB Output is correct
6 Correct 69 ms 111876 KB Output is correct
7 Correct 69 ms 111888 KB Output is correct
8 Correct 73 ms 111952 KB Output is correct
9 Correct 69 ms 111876 KB Output is correct
10 Correct 69 ms 111944 KB Output is correct
11 Correct 74 ms 112428 KB Output is correct
12 Correct 84 ms 113144 KB Output is correct
13 Correct 83 ms 113052 KB Output is correct
14 Correct 90 ms 113516 KB Output is correct
15 Correct 89 ms 113452 KB Output is correct
16 Correct 82 ms 112872 KB Output is correct
17 Correct 73 ms 112364 KB Output is correct
18 Correct 78 ms 112952 KB Output is correct
19 Runtime error 477 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -