oj.uz

Submission #539119

# Submission time Handle Problem Language Result Execution time Memory
539119 2022-03-18T12:32:50 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1129 ms 262144 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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 res[MX];


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


struct Seg {
	int mx[MX], t[MX];
	vi sl[MX];
	vector<pair<ii, int>> 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;
			ol[p] = 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]);
			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]);
		}
	}

	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, -1}, qid});
				rem[v].pb({{rp, 1}, qid});
			}

			maxeq(left_max, mx[v]);
		}

		res[qid] = ans;
	}

	void process() {
		for(int v = 1; v < 2 * n; v++) {
			sort(all(rem[v]));
			set<int> act;
			int i = 0;

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

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

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



void solve() {
	cin >> n >> q;
	vi a(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();
    }
}

Compilation message

sortbooks.cpp: In member function 'void Seg::process()':
sortbooks.cpp:109:9: warning: unused variable 'open' [-Wunused-variable]
  109 |     int open = p.F.S;
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111808 KB Output is correct
2 Correct 69 ms 111816 KB Output is correct
3 Correct 63 ms 111892 KB Output is correct
4 Correct 64 ms 111816 KB Output is correct
5 Correct 70 ms 111852 KB Output is correct
6 Correct 70 ms 111924 KB Output is correct
7 Correct 67 ms 111996 KB Output is correct
8 Correct 65 ms 111948 KB Output is correct
9 Correct 62 ms 111856 KB Output is correct
10 Correct 64 ms 111900 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111808 KB Output is correct
2 Correct 69 ms 111816 KB Output is correct
3 Correct 63 ms 111892 KB Output is correct
4 Correct 64 ms 111816 KB Output is correct
5 Correct 70 ms 111852 KB Output is correct
6 Correct 70 ms 111924 KB Output is correct
7 Correct 67 ms 111996 KB Output is correct
8 Correct 65 ms 111948 KB Output is correct
9 Correct 62 ms 111856 KB Output is correct
10 Correct 64 ms 111900 KB Output is correct
11 Correct 74 ms 112712 KB Output is correct
12 Correct 74 ms 113112 KB Output is correct
13 Correct 73 ms 113276 KB Output is correct
14 Correct 79 ms 113760 KB Output is correct
15 Correct 77 ms 113836 KB Output is correct
16 Correct 71 ms 112980 KB Output is correct
17 Correct 70 ms 112224 KB Output is correct
18 Correct 75 ms 113188 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 512 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 440 ms 154572 KB Output is correct
2 Correct 416 ms 158368 KB Output is correct
3 Correct 482 ms 146284 KB Output is correct
4 Correct 417 ms 145824 KB Output is correct
5 Correct 448 ms 144820 KB Output is correct
6 Correct 286 ms 142708 KB Output is correct
7 Correct 326 ms 142592 KB Output is correct
8 Correct 307 ms 142940 KB Output is correct
9 Correct 112 ms 112188 KB Output is correct
10 Correct 317 ms 140348 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111808 KB Output is correct
2 Correct 69 ms 111816 KB Output is correct
3 Correct 63 ms 111892 KB Output is correct
4 Correct 64 ms 111816 KB Output is correct
5 Correct 70 ms 111852 KB Output is correct
6 Correct 70 ms 111924 KB Output is correct
7 Correct 67 ms 111996 KB Output is correct
8 Correct 65 ms 111948 KB Output is correct
9 Correct 62 ms 111856 KB Output is correct
10 Correct 64 ms 111900 KB Output is correct
11 Correct 74 ms 112712 KB Output is correct
12 Correct 74 ms 113112 KB Output is correct
13 Correct 73 ms 113276 KB Output is correct
14 Correct 79 ms 113760 KB Output is correct
15 Correct 77 ms 113836 KB Output is correct
16 Correct 71 ms 112980 KB Output is correct
17 Correct 70 ms 112224 KB Output is correct
18 Correct 75 ms 113188 KB Output is correct
19 Correct 944 ms 205564 KB Output is correct
20 Correct 942 ms 205444 KB Output is correct
21 Correct 938 ms 211140 KB Output is correct
22 Correct 912 ms 211880 KB Output is correct
23 Correct 919 ms 211980 KB Output is correct
24 Correct 965 ms 180928 KB Output is correct
25 Correct 908 ms 180516 KB Output is correct
26 Correct 1129 ms 185712 KB Output is correct
27 Correct 985 ms 185780 KB Output is correct
28 Correct 1006 ms 186868 KB Output is correct
29 Correct 985 ms 184784 KB Output is correct
30 Correct 932 ms 184420 KB Output is correct
31 Correct 978 ms 186280 KB Output is correct
32 Correct 986 ms 186336 KB Output is correct
33 Correct 1014 ms 186396 KB Output is correct
34 Correct 739 ms 180160 KB Output is correct
35 Correct 760 ms 180044 KB Output is correct
36 Correct 738 ms 180260 KB Output is correct
37 Correct 763 ms 180052 KB Output is correct
38 Correct 794 ms 179848 KB Output is correct
39 Correct 559 ms 170076 KB Output is correct
40 Correct 258 ms 129348 KB Output is correct
41 Correct 535 ms 171260 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111808 KB Output is correct
2 Correct 69 ms 111816 KB Output is correct
3 Correct 63 ms 111892 KB Output is correct
4 Correct 64 ms 111816 KB Output is correct
5 Correct 70 ms 111852 KB Output is correct
6 Correct 70 ms 111924 KB Output is correct
7 Correct 67 ms 111996 KB Output is correct
8 Correct 65 ms 111948 KB Output is correct
9 Correct 62 ms 111856 KB Output is correct
10 Correct 64 ms 111900 KB Output is correct
11 Correct 74 ms 112712 KB Output is correct
12 Correct 74 ms 113112 KB Output is correct
13 Correct 73 ms 113276 KB Output is correct
14 Correct 79 ms 113760 KB Output is correct
15 Correct 77 ms 113836 KB Output is correct
16 Correct 71 ms 112980 KB Output is correct
17 Correct 70 ms 112224 KB Output is correct
18 Correct 75 ms 113188 KB Output is correct
19 Runtime error 512 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -