| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 699509 | 2023-02-17T08:30:33 Z | arcane | Alternating Heights (CCO22_day1problem1) | C++17 | 424 ms | 9184 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) ans[i] = max(i, ans[i - 1]);
if (ans[i] == n - 1) continue;
/*if (i == 1){
cerr << "Checking 1: \n"; check(4);
cerr << "DONE\n";
}*/
while (ans[i] < n and check(ans[i])) ans[i]++;
ans[i] -= 1;
}
}
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";
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 176 ms | 4032 KB | Output is correct |
| 2 | Correct | 181 ms | 3916 KB | Output is correct |
| 3 | Correct | 179 ms | 3884 KB | Output is correct |
| 4 | Correct | 151 ms | 3704 KB | Output is correct |
| 5 | Correct | 129 ms | 3776 KB | Output is correct |
| 6 | Correct | 187 ms | 3888 KB | Output is correct |
| 7 | Correct | 163 ms | 3940 KB | Output is correct |
| 8 | Correct | 193 ms | 3968 KB | Output is correct |
| 9 | Correct | 171 ms | 3944 KB | Output is correct |
| 10 | Correct | 207 ms | 4380 KB | Output is correct |
| 11 | Correct | 219 ms | 5024 KB | Output is correct |
| 12 | Correct | 243 ms | 4920 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 154 ms | 3832 KB | Output is correct |
| 2 | Correct | 146 ms | 3912 KB | Output is correct |
| 3 | Correct | 135 ms | 3784 KB | Output is correct |
| 4 | Correct | 130 ms | 4660 KB | Output is correct |
| 5 | Correct | 129 ms | 3972 KB | Output is correct |
| 6 | Correct | 168 ms | 3820 KB | Output is correct |
| 7 | Correct | 151 ms | 3844 KB | Output is correct |
| 8 | Correct | 136 ms | 3916 KB | Output is correct |
| 9 | Correct | 162 ms | 4200 KB | Output is correct |
| 10 | Correct | 143 ms | 4776 KB | Output is correct |
| 11 | Correct | 156 ms | 4868 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 254 ms | 560 KB | Output is correct |
| 3 | Correct | 263 ms | 592 KB | Output is correct |
| 4 | Correct | 7 ms | 596 KB | Output is correct |
| 5 | Correct | 1 ms | 468 KB | Output is correct |
| 6 | Correct | 1 ms | 468 KB | Output is correct |
| 7 | Correct | 163 ms | 580 KB | Output is correct |
| 8 | Correct | 233 ms | 572 KB | Output is correct |
| 9 | Correct | 282 ms | 588 KB | Output is correct |
| 10 | Correct | 123 ms | 576 KB | Output is correct |
| 11 | Correct | 140 ms | 552 KB | Output is correct |
| 12 | Correct | 99 ms | 696 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 176 ms | 4032 KB | Output is correct |
| 2 | Correct | 181 ms | 3916 KB | Output is correct |
| 3 | Correct | 179 ms | 3884 KB | Output is correct |
| 4 | Correct | 151 ms | 3704 KB | Output is correct |
| 5 | Correct | 129 ms | 3776 KB | Output is correct |
| 6 | Correct | 187 ms | 3888 KB | Output is correct |
| 7 | Correct | 163 ms | 3940 KB | Output is correct |
| 8 | Correct | 193 ms | 3968 KB | Output is correct |
| 9 | Correct | 171 ms | 3944 KB | Output is correct |
| 10 | Correct | 207 ms | 4380 KB | Output is correct |
| 11 | Correct | 219 ms | 5024 KB | Output is correct |
| 12 | Correct | 243 ms | 4920 KB | Output is correct |
| 13 | Correct | 154 ms | 3832 KB | Output is correct |
| 14 | Correct | 146 ms | 3912 KB | Output is correct |
| 15 | Correct | 135 ms | 3784 KB | Output is correct |
| 16 | Correct | 130 ms | 4660 KB | Output is correct |
| 17 | Correct | 129 ms | 3972 KB | Output is correct |
| 18 | Correct | 168 ms | 3820 KB | Output is correct |
| 19 | Correct | 151 ms | 3844 KB | Output is correct |
| 20 | Correct | 136 ms | 3916 KB | Output is correct |
| 21 | Correct | 162 ms | 4200 KB | Output is correct |
| 22 | Correct | 143 ms | 4776 KB | Output is correct |
| 23 | Correct | 156 ms | 4868 KB | Output is correct |
| 24 | Correct | 1 ms | 340 KB | Output is correct |
| 25 | Correct | 1 ms | 340 KB | Output is correct |
| 26 | Correct | 254 ms | 560 KB | Output is correct |
| 27 | Correct | 263 ms | 592 KB | Output is correct |
| 28 | Correct | 7 ms | 596 KB | Output is correct |
| 29 | Correct | 1 ms | 468 KB | Output is correct |
| 30 | Correct | 1 ms | 468 KB | Output is correct |
| 31 | Correct | 163 ms | 580 KB | Output is correct |
| 32 | Correct | 233 ms | 572 KB | Output is correct |
| 33 | Correct | 282 ms | 588 KB | Output is correct |
| 34 | Correct | 123 ms | 576 KB | Output is correct |
| 35 | Correct | 140 ms | 552 KB | Output is correct |
| 36 | Correct | 99 ms | 696 KB | Output is correct |
| 37 | Correct | 414 ms | 4568 KB | Output is correct |
| 38 | Correct | 424 ms | 4720 KB | Output is correct |
| 39 | Correct | 176 ms | 8124 KB | Output is correct |
| 40 | Correct | 118 ms | 8304 KB | Output is correct |
| 41 | Correct | 163 ms | 8600 KB | Output is correct |
| 42 | Correct | 353 ms | 8760 KB | Output is correct |
| 43 | Correct | 355 ms | 8996 KB | Output is correct |
| 44 | Correct | 274 ms | 8736 KB | Output is correct |
| 45 | Correct | 305 ms | 9104 KB | Output is correct |
| 46 | Correct | 311 ms | 9184 KB | Output is correct |
| 47 | Correct | 289 ms | 9104 KB | Output is correct |