Submission #851626

#	Time	Username	Problem	Language	Result	Execution time	Memory
851626		khanhphucscratch	Alternating Heights (CCO22_day1problem1)	C++14	4 / 25	221 ms	44440 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int a[3001], val[3001], pre[3001][3001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k, q;
    cin>>n>>k>>q;
    map<pair<int, int>, int> f;
    for(int i = 1; i <= n; i++) cin>>a[i];
    val[n] = 1e9;
    for(int i = n-1; i >= 1; i--){
        if(a[i] == a[i+1]) val[i] = i+1;
        else{
            pair<int, int> cap;
            if(i%2 == 1) cap = {a[i+1], a[i]}; //nguoc
            else cap = {a[i], a[i+1]};
            if(f[cap] > 0) val[i] = f[cap];
            else val[i] = 1e9;
            swap(cap.first, cap.second);
            f[cap] = i+1;
        }
    }
    for(int i = 1; i <= n; i++){
        pre[i][i] = val[i];
        for(int j = i+1; j <= n; j++) pre[i][j] = min(pre[i][j-1], val[j]);
    }
    for(int i = 1; i <= q; i++){
        int l, r;
        cin>>l>>r;
        if(pre[l][r] <= r) cout<<"NO"<<'\n';
        else cout<<"YES"<<'\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8