oj.uz

Submission #851507

# Submission time Handle Problem Language Result Execution time Memory
851507 2023-09-20T02:52:01 Z Tuanlinh123 Alternating Heights (CCO22_day1problem1) C++17
0 / 25
 214 ms 83024 KB 
#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.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 8.0

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