oj.uz

Submission #699473

# Submission time Handle Problem Language Result Execution time Memory
699473 2023-02-17T04:54:46 Z arcane Alternating Heights (CCO22_day1problem1) C++17
6 / 25
 1000 ms 9056 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;
vector <int> edg[MAX_N], topo;
int arr[MAX_N], ans[MAX_N], cur;
bool marked[MAX_N], flag;
int n;
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 <= n; i++) edg[i].clear();
	topo.clear(); fill(marked, marked + MAX_N, 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 (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 + MAX_N, 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';
			}*/
		}
	}
	for (int i = 0; i < n; i++){
		for (auto nx : edg[i]) if (nx == i) flag = true;
	}
	//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 k, 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 8488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 9056 KB Output is correct
2 Correct 163 ms 7152 KB Output is correct
3 Correct 163 ms 7184 KB Output is correct
4 Correct 113 ms 8136 KB Output is correct
5 Correct 127 ms 7332 KB Output is correct
6 Correct 166 ms 7216 KB Output is correct
7 Correct 163 ms 7220 KB Output is correct
8 Correct 164 ms 7356 KB Output is correct
9 Correct 225 ms 7680 KB Output is correct
10 Correct 190 ms 8176 KB Output is correct
11 Correct 167 ms 8152 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1093 ms 720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 8488 KB Time limit exceeded
2 Halted 0 ms 0 KB -