oj.uz

Submission #538977

# Submission time Handle Problem Language Result Execution time Memory
538977 2022-03-18T06:33:51 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2082 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 = 4 * 1000 * 1000;


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

	Seg(vi& a) {
		forn(i, MX)
			mx[i] = t[i] = -INF;
//		mx.assign(4 * n, -INF);
//		t.assign(4 * n, -INF);
//		sl.resize(4 * n);

		build(a);
	}

	void build(vi& a, int v = 1, int tl = 0, int tr = n - 1) {
		if(tl == tr) {
			mx[v] = a[tl];
			sl[v].pb(a[tl]);
			return;
		}
		int tm = (tl + tr) / 2;

		build(a, 2 * v, tl, tm);
		build(a, 2 * v + 1, tm + 1, tr);

		mx[v] = max(mx[2 * v], mx[2 * v + 1]);
		merge(all(sl[2 * v]), all(sl[2 * v + 1]), back_inserter(sl[v]));

		t[v] = max(t[2 * v], t[2 * v + 1]);
		int ind = lower_bound(all(sl[2 * v + 1]), mx[2 * v]) - sl[2 * v + 1].begin();
		if(ind != 0)
			maxeq(t[v], mx[2 * v] + sl[2 * v + 1][ind - 1]);
	}

	pair<bool, int> query(int l, int r, int k, int left_max, int v = 1, int tl = 0, int tr = n - 1) {
		if(l > r)
			return {true, -INF};
		if(tl == l && r == tr) {
			bool ans = t[v] <= k;
			int rp = left_max - 1, lp = k - left_max + 1;

			if(lp <= rp) {
				int indl = lower_bound(all(sl[v]), lp) - sl[v].begin();
				int indr = lower_bound(all(sl[v]), rp + 1) - sl[v].begin();

				ans = ans && indl == indr;
			}
			return {ans, mx[v]};
		}
		int tm = (tl + tr) / 2;

		auto q1 = query(l, min(r, tm), k, left_max, 2 * v, tl, tm);
		auto q2 = query(max(l, tm + 1), r, k, max(left_max, q1.S), 2 * v + 1, tm + 1, tr);

		return {q1.F && q2.F, max(q1.S, q2.S)};
	}
};



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

	Seg seg(a);

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

		auto ans = seg.query(l, r, k, -INF);
		cout << ans.F << '\n';
	}

//	forn(k, 15) {
//		auto ans = seg.query(0, n - 1, k, (k + 1) / 2, (k - 1) / 2);
//		cout << k << ' ' << ans.F << '\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 72 ms 125496 KB Output is correct
2 Correct 74 ms 125480 KB Output is correct
3 Correct 81 ms 125472 KB Output is correct
4 Correct 78 ms 125432 KB Output is correct
5 Correct 73 ms 125456 KB Output is correct
6 Correct 75 ms 125624 KB Output is correct
7 Correct 71 ms 125560 KB Output is correct
8 Correct 71 ms 125548 KB Output is correct
9 Correct 75 ms 125572 KB Output is correct
10 Correct 73 ms 125544 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125496 KB Output is correct
2 Correct 74 ms 125480 KB Output is correct
3 Correct 81 ms 125472 KB Output is correct
4 Correct 78 ms 125432 KB Output is correct
5 Correct 73 ms 125456 KB Output is correct
6 Correct 75 ms 125624 KB Output is correct
7 Correct 71 ms 125560 KB Output is correct
8 Correct 71 ms 125548 KB Output is correct
9 Correct 75 ms 125572 KB Output is correct
10 Correct 73 ms 125544 KB Output is correct
11 Correct 78 ms 125772 KB Output is correct
12 Correct 77 ms 126300 KB Output is correct
13 Correct 75 ms 126232 KB Output is correct
14 Correct 85 ms 126368 KB Output is correct
15 Correct 83 ms 126348 KB Output is correct
16 Correct 84 ms 126440 KB Output is correct
17 Correct 76 ms 126204 KB Output is correct
18 Correct 74 ms 126212 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2082 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 412 ms 139448 KB Output is correct
2 Correct 316 ms 139336 KB Output is correct
3 Correct 271 ms 139368 KB Output is correct
4 Correct 257 ms 140452 KB Output is correct
5 Correct 254 ms 140508 KB Output is correct
6 Correct 201 ms 140592 KB Output is correct
7 Correct 208 ms 140552 KB Output is correct
8 Correct 242 ms 140484 KB Output is correct
9 Correct 108 ms 126924 KB Output is correct
10 Correct 197 ms 140492 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125496 KB Output is correct
2 Correct 74 ms 125480 KB Output is correct
3 Correct 81 ms 125472 KB Output is correct
4 Correct 78 ms 125432 KB Output is correct
5 Correct 73 ms 125456 KB Output is correct
6 Correct 75 ms 125624 KB Output is correct
7 Correct 71 ms 125560 KB Output is correct
8 Correct 71 ms 125548 KB Output is correct
9 Correct 75 ms 125572 KB Output is correct
10 Correct 73 ms 125544 KB Output is correct
11 Correct 78 ms 125772 KB Output is correct
12 Correct 77 ms 126300 KB Output is correct
13 Correct 75 ms 126232 KB Output is correct
14 Correct 85 ms 126368 KB Output is correct
15 Correct 83 ms 126348 KB Output is correct
16 Correct 84 ms 126440 KB Output is correct
17 Correct 76 ms 126204 KB Output is correct
18 Correct 74 ms 126212 KB Output is correct
19 Correct 865 ms 155072 KB Output is correct
20 Correct 885 ms 155008 KB Output is correct
21 Correct 707 ms 155200 KB Output is correct
22 Correct 748 ms 155052 KB Output is correct
23 Correct 662 ms 155160 KB Output is correct
24 Correct 403 ms 155000 KB Output is correct
25 Correct 448 ms 155088 KB Output is correct
26 Correct 514 ms 155064 KB Output is correct
27 Correct 515 ms 154996 KB Output is correct
28 Correct 562 ms 155024 KB Output is correct
29 Correct 581 ms 154996 KB Output is correct
30 Correct 542 ms 155084 KB Output is correct
31 Correct 567 ms 155228 KB Output is correct
32 Correct 562 ms 155180 KB Output is correct
33 Correct 556 ms 155100 KB Output is correct
34 Correct 430 ms 155164 KB Output is correct
35 Correct 396 ms 155028 KB Output is correct
36 Correct 377 ms 155100 KB Output is correct
37 Correct 377 ms 155064 KB Output is correct
38 Correct 378 ms 155072 KB Output is correct
39 Correct 412 ms 155016 KB Output is correct
40 Correct 268 ms 143260 KB Output is correct
41 Correct 421 ms 155092 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125496 KB Output is correct
2 Correct 74 ms 125480 KB Output is correct
3 Correct 81 ms 125472 KB Output is correct
4 Correct 78 ms 125432 KB Output is correct
5 Correct 73 ms 125456 KB Output is correct
6 Correct 75 ms 125624 KB Output is correct
7 Correct 71 ms 125560 KB Output is correct
8 Correct 71 ms 125548 KB Output is correct
9 Correct 75 ms 125572 KB Output is correct
10 Correct 73 ms 125544 KB Output is correct
11 Correct 78 ms 125772 KB Output is correct
12 Correct 77 ms 126300 KB Output is correct
13 Correct 75 ms 126232 KB Output is correct
14 Correct 85 ms 126368 KB Output is correct
15 Correct 83 ms 126348 KB Output is correct
16 Correct 84 ms 126440 KB Output is correct
17 Correct 76 ms 126204 KB Output is correct
18 Correct 74 ms 126212 KB Output is correct
19 Runtime error 2082 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -