oj.uz

답안 #539146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539146 2022-03-18T13:32:29 Z akhan42 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 261052 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)
			vi().swap(sl[i]);
	}

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

			vii().swap(rem[v]);
		}
	}
};



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

	Seg seg(a);
	int qq = q / 4;

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

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

		if(qid == qq || qid == 2 * qq || qid == 3 * qq) {
			seg.process();
		}
	}

	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

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 111756 KB Output is correct
2 Correct 79 ms 111856 KB Output is correct
3 Correct 72 ms 111864 KB Output is correct
4 Correct 71 ms 111848 KB Output is correct
5 Correct 72 ms 111768 KB Output is correct
6 Correct 82 ms 111812 KB Output is correct
7 Correct 75 ms 111860 KB Output is correct
8 Correct 81 ms 111916 KB Output is correct
9 Correct 70 ms 111816 KB Output is correct
10 Correct 72 ms 111816 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 111756 KB Output is correct
2 Correct 79 ms 111856 KB Output is correct
3 Correct 72 ms 111864 KB Output is correct
4 Correct 71 ms 111848 KB Output is correct
5 Correct 72 ms 111768 KB Output is correct
6 Correct 82 ms 111812 KB Output is correct
7 Correct 75 ms 111860 KB Output is correct
8 Correct 81 ms 111916 KB Output is correct
9 Correct 70 ms 111816 KB Output is correct
10 Correct 72 ms 111816 KB Output is correct
11 Correct 82 ms 111960 KB Output is correct
12 Correct 99 ms 112480 KB Output is correct
13 Correct 102 ms 112524 KB Output is correct
14 Correct 98 ms 112460 KB Output is correct
15 Correct 100 ms 112444 KB Output is correct
16 Correct 87 ms 112436 KB Output is correct
17 Correct 76 ms 112248 KB Output is correct
18 Correct 84 ms 112496 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3076 ms 261052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 847 ms 125768 KB Output is correct
2 Correct 859 ms 125792 KB Output is correct
3 Correct 578 ms 125768 KB Output is correct
4 Correct 564 ms 125784 KB Output is correct
5 Correct 570 ms 125768 KB Output is correct
6 Correct 452 ms 125792 KB Output is correct
7 Correct 468 ms 125844 KB Output is correct
8 Correct 487 ms 125828 KB Output is correct
9 Correct 114 ms 112076 KB Output is correct
10 Correct 416 ms 125776 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 111756 KB Output is correct
2 Correct 79 ms 111856 KB Output is correct
3 Correct 72 ms 111864 KB Output is correct
4 Correct 71 ms 111848 KB Output is correct
5 Correct 72 ms 111768 KB Output is correct
6 Correct 82 ms 111812 KB Output is correct
7 Correct 75 ms 111860 KB Output is correct
8 Correct 81 ms 111916 KB Output is correct
9 Correct 70 ms 111816 KB Output is correct
10 Correct 72 ms 111816 KB Output is correct
11 Correct 82 ms 111960 KB Output is correct
12 Correct 99 ms 112480 KB Output is correct
13 Correct 102 ms 112524 KB Output is correct
14 Correct 98 ms 112460 KB Output is correct
15 Correct 100 ms 112444 KB Output is correct
16 Correct 87 ms 112436 KB Output is correct
17 Correct 76 ms 112248 KB Output is correct
18 Correct 84 ms 112496 KB Output is correct
19 Correct 2114 ms 140516 KB Output is correct
20 Correct 2049 ms 140604 KB Output is correct
21 Correct 2027 ms 140584 KB Output is correct
22 Correct 2008 ms 140648 KB Output is correct
23 Correct 2025 ms 140628 KB Output is correct
24 Correct 1127 ms 140620 KB Output is correct
25 Correct 1108 ms 140612 KB Output is correct
26 Correct 1309 ms 140564 KB Output is correct
27 Correct 1254 ms 140552 KB Output is correct
28 Correct 1256 ms 140588 KB Output is correct
29 Correct 1200 ms 140508 KB Output is correct
30 Correct 1236 ms 140568 KB Output is correct
31 Correct 1244 ms 140588 KB Output is correct
32 Correct 1281 ms 140504 KB Output is correct
33 Correct 1242 ms 140512 KB Output is correct
34 Correct 1095 ms 140612 KB Output is correct
35 Correct 1034 ms 140516 KB Output is correct
36 Correct 1091 ms 140564 KB Output is correct
37 Correct 1051 ms 140612 KB Output is correct
38 Correct 1049 ms 140624 KB Output is correct
39 Correct 1175 ms 140612 KB Output is correct
40 Correct 543 ms 130008 KB Output is correct
41 Correct 879 ms 140612 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 111756 KB Output is correct
2 Correct 79 ms 111856 KB Output is correct
3 Correct 72 ms 111864 KB Output is correct
4 Correct 71 ms 111848 KB Output is correct
5 Correct 72 ms 111768 KB Output is correct
6 Correct 82 ms 111812 KB Output is correct
7 Correct 75 ms 111860 KB Output is correct
8 Correct 81 ms 111916 KB Output is correct
9 Correct 70 ms 111816 KB Output is correct
10 Correct 72 ms 111816 KB Output is correct
11 Correct 82 ms 111960 KB Output is correct
12 Correct 99 ms 112480 KB Output is correct
13 Correct 102 ms 112524 KB Output is correct
14 Correct 98 ms 112460 KB Output is correct
15 Correct 100 ms 112444 KB Output is correct
16 Correct 87 ms 112436 KB Output is correct
17 Correct 76 ms 112248 KB Output is correct
18 Correct 84 ms 112496 KB Output is correct
19 Execution timed out 3076 ms 261052 KB Time limit exceeded
20 Halted 0 ms 0 KB -