oj.uz

Submission #851645

# Submission time Handle Problem Language Result Execution time Memory
851645 2023-09-20T10:15:17 Z khanhphucscratch Alternating Heights (CCO22_day1problem1) C++14
11 / 25
 163 ms 4432 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> ad[3001];
int k, c[3001], f[3001], a[3001], val[3001], state[3001];
bool ok = 1;
void dfs(int u)
{
    state[u] = 1;
    for(int v : ad[u]) if(state[v] < 2){
        if(state[v] == 1){ok = 0; return;}
        else{
            dfs(v);
            if(ok == 0) return;
        }
    }
    state[u] = 2;
}
bool check(int l, int r)
{
    for(int i = 1; i <= k; i++){
        ad[i].clear();
        f[i] = 0; state[i] = 0; c[i] = 0;
    }
    for(int i = l; i <= r; i++){
        c[a[i]]++;
        if(i%2 == 1){
            if(i-1 >= l){
                ad[a[i]].push_back(a[i-1]);
                f[a[i-1]]++;
            }
            if(i+1 <= r){
                ad[a[i]].push_back(a[i+1]);
                f[a[i+1]]++;
            }
        }
    }
    ok = 0;
    for(int i = 1; i <= k; i++) if(f[i] == 0 && c[i] > 0){
        ok = 1;
        dfs(i);
        if(ok == 0) return 0;
    }
    return ok;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin>>n>>k>>q;
    map<pair<int, int>, int> f;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int j = 1;
    for(int i = 1; i <= n; i++){
        while(j <= n && check(i, j) == 1) j++;
        val[i] = j;
    }
    for(int i = 1; i <= q; i++){
        int l, r;
        cin>>l>>r;
        if(val[l] <= r) cout<<"NO"<<'\n';
        else cout<<"YES"<<'\n';
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3412 KB Output is correct
2 Correct 135 ms 3404 KB Output is correct
3 Correct 142 ms 3664 KB Output is correct
4 Correct 105 ms 3664 KB Output is correct
5 Correct 113 ms 3440 KB Output is correct
6 Correct 133 ms 3412 KB Output is correct
7 Correct 139 ms 3408 KB Output is correct
8 Correct 146 ms 3580 KB Output is correct
9 Correct 145 ms 3604 KB Output is correct
10 Correct 163 ms 4260 KB Output is correct
11 Correct 150 ms 4432 KB Output is correct
12 Correct 162 ms 4432 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 3600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 49 ms 836 KB Output is correct
3 Correct 54 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 532 KB Output is correct
7 Correct 36 ms 612 KB Output is correct
8 Correct 65 ms 636 KB Output is correct
9 Correct 84 ms 860 KB Output is correct
10 Correct 54 ms 600 KB Output is correct
11 Correct 73 ms 624 KB Output is correct
12 Correct 47 ms 600 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3412 KB Output is correct
2 Correct 135 ms 3404 KB Output is correct
3 Correct 142 ms 3664 KB Output is correct
4 Correct 105 ms 3664 KB Output is correct
5 Correct 113 ms 3440 KB Output is correct
6 Correct 133 ms 3412 KB Output is correct
7 Correct 139 ms 3408 KB Output is correct
8 Correct 146 ms 3580 KB Output is correct
9 Correct 145 ms 3604 KB Output is correct
10 Correct 163 ms 4260 KB Output is correct
11 Correct 150 ms 4432 KB Output is correct
12 Correct 162 ms 4432 KB Output is correct
13 Incorrect 128 ms 3600 KB Output isn't correct
14 Halted 0 ms 0 KB -