oj.uz

Submission #620630

# Submission time Handle Problem Language Result Execution time Memory
620630 2022-08-03T07:42:26 Z Theo830 Alternating Heights (CCO22_day1problem1) C++17
25 / 25
 609 ms 13772 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll n;
vector<vll>in;
ll out[3005] = {0};
bool check(vll arr){
    f(i,0,n){
        out[i] = 0;
    }
    in.assign(n,vll());
    ll posoi = 0;
    queue<ll>q;
    f(i,0,(ll)arr.size()-1){
        if(i % 2 == 0){
            out[arr[i]]++;
            in[arr[i+1]].pb(arr[i]);
        }
        else{
            out[arr[i+1]]++;
            in[arr[i]].pb(arr[i+1]);
        }
    }
    f(i,0,n){
        if(out[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        ll f = q.front();
        q.pop();
        posoi++;
        for(auto x:in[f]){
            out[x]--;
            if(out[x] == 0){
                q.push(x);
            }
        }
    }
    return posoi == n;
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll k,q;
    cin>>n>>k>>q;
    ll arr[n];
    f(i,0,n){
        cin>>arr[i];
    }
    ll ans[n];
    ll pos[2] = {0,1};
    f(i,0,n){
        while(pos[i % 2] < n){
            vll ex;
            f(j,i,pos[i % 2] + 1){
                ex.pb(arr[j]-1);
            }
            if(check(ex)){
                pos[i % 2]++;
            }
            else{
                break;
            }
        }
        ans[i] = pos[i % 2] - 1;
    }
    while(q--){
        ll x,y;
        cin>>x>>y;
        if(ans[x-1] >= y-1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 5076 KB Output is correct
2 Correct 454 ms 4468 KB Output is correct
3 Correct 460 ms 11848 KB Output is correct
4 Correct 120 ms 6836 KB Output is correct
5 Correct 137 ms 8804 KB Output is correct
6 Correct 436 ms 11592 KB Output is correct
7 Correct 447 ms 12236 KB Output is correct
8 Correct 507 ms 12428 KB Output is correct
9 Correct 478 ms 12052 KB Output is correct
10 Correct 494 ms 12440 KB Output is correct
11 Correct 448 ms 12824 KB Output is correct
12 Correct 609 ms 12188 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 4440 KB Output is correct
2 Correct 185 ms 10044 KB Output is correct
3 Correct 172 ms 9912 KB Output is correct
4 Correct 121 ms 8008 KB Output is correct
5 Correct 148 ms 8784 KB Output is correct
6 Correct 154 ms 9880 KB Output is correct
7 Correct 158 ms 9992 KB Output is correct
8 Correct 153 ms 9948 KB Output is correct
9 Correct 164 ms 10348 KB Output is correct
10 Correct 152 ms 10852 KB Output is correct
11 Correct 151 ms 10996 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 393 ms 736 KB Output is correct
3 Correct 402 ms 700 KB Output is correct
4 Correct 270 ms 492 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 348 ms 580 KB Output is correct
8 Correct 423 ms 744 KB Output is correct
9 Correct 469 ms 676 KB Output is correct
10 Correct 376 ms 776 KB Output is correct
11 Correct 397 ms 672 KB Output is correct
12 Correct 344 ms 728 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 5076 KB Output is correct
2 Correct 454 ms 4468 KB Output is correct
3 Correct 460 ms 11848 KB Output is correct
4 Correct 120 ms 6836 KB Output is correct
5 Correct 137 ms 8804 KB Output is correct
6 Correct 436 ms 11592 KB Output is correct
7 Correct 447 ms 12236 KB Output is correct
8 Correct 507 ms 12428 KB Output is correct
9 Correct 478 ms 12052 KB Output is correct
10 Correct 494 ms 12440 KB Output is correct
11 Correct 448 ms 12824 KB Output is correct
12 Correct 609 ms 12188 KB Output is correct
13 Correct 149 ms 4440 KB Output is correct
14 Correct 185 ms 10044 KB Output is correct
15 Correct 172 ms 9912 KB Output is correct
16 Correct 121 ms 8008 KB Output is correct
17 Correct 148 ms 8784 KB Output is correct
18 Correct 154 ms 9880 KB Output is correct
19 Correct 158 ms 9992 KB Output is correct
20 Correct 153 ms 9948 KB Output is correct
21 Correct 164 ms 10348 KB Output is correct
22 Correct 152 ms 10852 KB Output is correct
23 Correct 151 ms 10996 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 393 ms 736 KB Output is correct
27 Correct 402 ms 700 KB Output is correct
28 Correct 270 ms 492 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 348 ms 580 KB Output is correct
32 Correct 423 ms 744 KB Output is correct
33 Correct 469 ms 676 KB Output is correct
34 Correct 376 ms 776 KB Output is correct
35 Correct 397 ms 672 KB Output is correct
36 Correct 344 ms 728 KB Output is correct
37 Correct 573 ms 12720 KB Output is correct
38 Correct 569 ms 12648 KB Output is correct
39 Correct 469 ms 11972 KB Output is correct
40 Correct 119 ms 7760 KB Output is correct
41 Correct 152 ms 9088 KB Output is correct
42 Correct 527 ms 13048 KB Output is correct
43 Correct 574 ms 13164 KB Output is correct
44 Correct 525 ms 13124 KB Output is correct
45 Correct 558 ms 13156 KB Output is correct
46 Correct 559 ms 13544 KB Output is correct
47 Correct 549 ms 13772 KB Output is correct