oj.uz

Submission #743579

# Submission time Handle Problem Language Result Execution time Memory
743579 2023-05-17T14:09:50 Z flappybird Alternating Heights (CCO22_day1problem1) C++17
10 / 25
 1000 ms 18496 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int last[MAX];
vector<int> adj[MAX];
int vis[MAX];
bool dfs(int x) {
	if (vis[x]) return !~vis[x];
	vis[x] = -1;
	for (auto v : adj[x]) if (dfs(v)) return true;
	vis[x] = 1;
	return false;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	int Q;
	cin >> N >> K;
	cin >> Q;
	int i, j;
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) {
		int l, r;
		l = i;
		r = N + 1;
		while (r - l > 1) {
			int m = l + r >> 1;
			for (j = 1; j <= K; j++) adj[j].clear(), vis[j] = 0;
			int c = 0;
			for (j = i + 1; j <= m; j++) {
				if (c) adj[A[j]].push_back(A[j - 1]);
				else adj[A[j - 1]].push_back(A[j]);
				c ^= 1;
			}
			c = 0;
			for (j = 1; j <= K; j++) if (!vis[j]) {
				if (dfs(j)) {
					c = 1;
					break;
				}
			}
			if (c) r = m;
			else l = m;
		}
		last[i] = l;
	}
	while (Q--) {
		int a, b;
		cin >> a >> b;
		if (last[a] < b) cout << "NO" << ln;
		else cout << "YES" << ln;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |    int m = l + r >> 1;
      |            ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 17356 KB Output is correct
2 Correct 220 ms 17492 KB Output is correct
3 Correct 216 ms 17352 KB Output is correct
4 Correct 149 ms 11944 KB Output is correct
5 Correct 161 ms 13972 KB Output is correct
6 Correct 216 ms 17484 KB Output is correct
7 Correct 226 ms 17424 KB Output is correct
8 Correct 228 ms 17520 KB Output is correct
9 Correct 245 ms 17484 KB Output is correct
10 Correct 329 ms 17856 KB Output is correct
11 Correct 508 ms 18496 KB Output is correct
12 Correct 482 ms 17712 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 15680 KB Output is correct
2 Correct 181 ms 15636 KB Output is correct
3 Correct 173 ms 15572 KB Output is correct
4 Correct 151 ms 13052 KB Output is correct
5 Correct 171 ms 14028 KB Output is correct
6 Correct 172 ms 15808 KB Output is correct
7 Correct 186 ms 15648 KB Output is correct
8 Correct 215 ms 15724 KB Output is correct
9 Correct 215 ms 16140 KB Output is correct
10 Correct 195 ms 16536 KB Output is correct
11 Correct 223 ms 16588 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 444 ms 5176 KB Output is correct
3 Correct 534 ms 5164 KB Output is correct
4 Correct 36 ms 5104 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 353 ms 5260 KB Output is correct
8 Correct 669 ms 5148 KB Output is correct
9 Correct 867 ms 5288 KB Output is correct
10 Correct 914 ms 5140 KB Output is correct
11 Execution timed out 1070 ms 5164 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 17356 KB Output is correct
2 Correct 220 ms 17492 KB Output is correct
3 Correct 216 ms 17352 KB Output is correct
4 Correct 149 ms 11944 KB Output is correct
5 Correct 161 ms 13972 KB Output is correct
6 Correct 216 ms 17484 KB Output is correct
7 Correct 226 ms 17424 KB Output is correct
8 Correct 228 ms 17520 KB Output is correct
9 Correct 245 ms 17484 KB Output is correct
10 Correct 329 ms 17856 KB Output is correct
11 Correct 508 ms 18496 KB Output is correct
12 Correct 482 ms 17712 KB Output is correct
13 Correct 181 ms 15680 KB Output is correct
14 Correct 181 ms 15636 KB Output is correct
15 Correct 173 ms 15572 KB Output is correct
16 Correct 151 ms 13052 KB Output is correct
17 Correct 171 ms 14028 KB Output is correct
18 Correct 172 ms 15808 KB Output is correct
19 Correct 186 ms 15648 KB Output is correct
20 Correct 215 ms 15724 KB Output is correct
21 Correct 215 ms 16140 KB Output is correct
22 Correct 195 ms 16536 KB Output is correct
23 Correct 223 ms 16588 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 444 ms 5176 KB Output is correct
27 Correct 534 ms 5164 KB Output is correct
28 Correct 36 ms 5104 KB Output is correct
29 Correct 4 ms 5076 KB Output is correct
30 Correct 4 ms 5076 KB Output is correct
31 Correct 353 ms 5260 KB Output is correct
32 Correct 669 ms 5148 KB Output is correct
33 Correct 867 ms 5288 KB Output is correct
34 Correct 914 ms 5140 KB Output is correct
35 Execution timed out 1070 ms 5164 KB Time limit exceeded
36 Halted 0 ms 0 KB -