oj.uz

Submission #699483

# Submission time Handle Problem Language Result Execution time Memory
699483 2023-02-17T05:13:25 Z arcane Alternating Heights (CCO22_day1problem1) C++17
10 / 25
 1000 ms 4576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
const int MAX_N = 5005;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
vector <int> edg[MAX_N], topo;
int arr[MAX_N], ans[MAX_N], cur;
bool marked[MAX_N], flag;
int n, k;
void dfs(int x){
	marked[x] = true;
	for (auto edge : edg[x]){
		if (!marked[edge]) dfs(edge);
	}
	topo.pb(x);
}
void dfs2(int x){
	if (marked[x]) return;
	marked[x] = true;
	for (auto edge : edg[x]){
		if (!marked[edge]) flag = true;
	}
}
bool check(int x){
	//if (cur == 1) cerr << cur << ' ' << x << '\n';
	for (int i = 0; i < k; i++) edg[i].clear();
	topo.clear(); fill(marked, marked + k, 0);
	for (int i = cur; i < x; i++){
		if ((i - cur) % 2) edg[arr[i]].pb(arr[i + 1]);
		else edg[arr[i + 1]].pb(arr[i]);
        if (arr[i] == arr[i + 1]) return false;
		/*if (cur == 1){
			if ((i - cur) % 2) cerr << arr[i] << ' ' << arr[i + 1] << '\n';
			else cerr << arr[i + 1] << ' ' << arr[i] << '\n';
		}*/
	}
	for (int i = 0; i < n; i++){
		if (!marked[i]) dfs(i);
	}
	//reverse(topo.begin(), topo.end());
	//if (cur == 1) for (auto tmp : topo) cerr << tmp << ' ';
	//if (cur == 1) cerr << '\n';
	fill(marked, marked + k, 0);
	flag = false;
	for (auto nod : topo){
		if (!marked[nod]){
			dfs2(nod);
			/*if (cur == 1){
				cerr << nod << ' ' << flag << '\n';
				for (int j = 0; j < 3; j++) cerr << marked[j] << ' ';
				cerr << '\n';
			}*/
		}
	}
	//if (cur == 1) cerr << '\n';
	return !flag;
}
void init(){
	for (int i = 0; i < n; i++){
		int lo = i, hi = n, mi; cur = i;
		/*if (i == 1){
			cerr << "Checking 1: \n"; check(4);
			cerr << "DONE\n";
		}*/
		while (lo + 1 != hi){
			mi = (lo + hi) / 2; 
			if (check(mi)) lo = mi;
			else hi = mi;
			//cerr << i << ' ' << lo << ' ' << hi << '\n';
		}
		ans[i] = lo;
	}
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int q, x, y; cin >> n >> k >> q;
	for (int i = 0; i < n; i++) cin >> arr[i], arr[i] -= 1;
	init();
	//for (int i = 0; i < n; i++) cerr << "Highest: " << ans[i] << '\n';
	for (int i = 0; i < q; i++){
		cin >> x >> y;
		x -= 1; y -= 1;
		if (y <= ans[x]) cout << "YES\n";
		else cout << "NO\n";
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 3444 KB Output is correct
2 Correct 151 ms 3476 KB Output is correct
3 Correct 172 ms 3456 KB Output is correct
4 Correct 115 ms 3428 KB Output is correct
5 Correct 122 ms 3556 KB Output is correct
6 Correct 149 ms 3516 KB Output is correct
7 Correct 167 ms 3496 KB Output is correct
8 Correct 161 ms 3540 KB Output is correct
9 Correct 192 ms 3588 KB Output is correct
10 Correct 281 ms 4004 KB Output is correct
11 Correct 434 ms 4576 KB Output is correct
12 Correct 404 ms 4520 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 3532 KB Output is correct
2 Correct 137 ms 3432 KB Output is correct
3 Correct 153 ms 3376 KB Output is correct
4 Correct 110 ms 4388 KB Output is correct
5 Correct 126 ms 3580 KB Output is correct
6 Correct 141 ms 3524 KB Output is correct
7 Correct 143 ms 3472 KB Output is correct
8 Correct 136 ms 3584 KB Output is correct
9 Correct 144 ms 3792 KB Output is correct
10 Correct 141 ms 4424 KB Output is correct
11 Correct 141 ms 4468 KB Output is correct
12 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 981 ms 568 KB Output is correct
3 Execution timed out 1045 ms 604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 3444 KB Output is correct
2 Correct 151 ms 3476 KB Output is correct
3 Correct 172 ms 3456 KB Output is correct
4 Correct 115 ms 3428 KB Output is correct
5 Correct 122 ms 3556 KB Output is correct
6 Correct 149 ms 3516 KB Output is correct
7 Correct 167 ms 3496 KB Output is correct
8 Correct 161 ms 3540 KB Output is correct
9 Correct 192 ms 3588 KB Output is correct
10 Correct 281 ms 4004 KB Output is correct
11 Correct 434 ms 4576 KB Output is correct
12 Correct 404 ms 4520 KB Output is correct
13 Correct 154 ms 3532 KB Output is correct
14 Correct 137 ms 3432 KB Output is correct
15 Correct 153 ms 3376 KB Output is correct
16 Correct 110 ms 4388 KB Output is correct
17 Correct 126 ms 3580 KB Output is correct
18 Correct 141 ms 3524 KB Output is correct
19 Correct 143 ms 3472 KB Output is correct
20 Correct 136 ms 3584 KB Output is correct
21 Correct 144 ms 3792 KB Output is correct
22 Correct 141 ms 4424 KB Output is correct
23 Correct 141 ms 4468 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 981 ms 568 KB Output is correct
27 Execution timed out 1045 ms 604 KB Time limit exceeded
28 Halted 0 ms 0 KB -