Submission #851507

#	Time	Username	Problem	Language	Result	Execution time	Memory
851507		Tuanlinh123	Alternating Heights (CCO22_day1problem1)	C++17	0 / 25	214 ms	83024 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

ll a[3005], c[3005], Time;;
ll ans[3005][3005];
vector <ll> A[3005];

bool dfs(ll u)
{
    c[u]=1;
    for (ll v:A[u])
    {
        if (!c[v])
        {
            if (!dfs(v))
                return 0;
        }
        else if (c[v]==1)
            return 0;
    }
    c[u]=2;
    return 1;
}

bool check(ll l, ll r)
{
    for (ll i=l; i<=r; i++)
        A[a[i]].clear(), c[a[i]]=0;
    ll crr=0; Time=0;
    for (ll i=l; i<r; i++)
    {
        if (crr) A[a[i]].pb(a[i+1]);
        else A[a[i+1]].pb(a[i]);
        if (a[i+1]==a[i]) return 0;
        crr^=1;
    }
    bool ok=1;
    for (ll i=l; i<=r; i++)
        if (!c[a[i]])
            ok&=dfs(a[i]);
    return ok;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k, q; cin >> n >> k >> q;
    for (ll i=1; i<=n; i++)
        cin >> a[i];
    for (ll i=1; i<=n; i++)
    {
        ll lo=i+1, hi=n+1;
        while (hi>lo)
        {
            ll mid=(hi+lo)/2;
            if (check(i, mid))
                lo=mid+1;
            else hi=mid;
        }
        cout << lo << "\n";
        for (ll j=i; j<lo; j++)
            ans[i][j]=1;
    }
    for (ll i=1; i<=q; i++)
    {
        ll l, r; cin >> l >> r;
        if (ans[l][r]) cout << "YES\n";
        else cout << "NO\n";
    }
}

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