Submission #936250

#	Time	Username	Problem	Language	Result	Execution time	Memory
936250		sleepntsheep	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	475 ms	14136 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 3005


int n, k, q, a[N], L[N];


basic_string<int> g[N];
int vs[N];

int cyclic(int u)
{
    vs[u] = 1;
    for (int v : g[u])
        if (vs[v] == 1 || !vs[v] && cyclic(v)) return 1;
    vs[u] = 2;
    return 0;
}

int main()
{
    ShinLena;
    cin >> n >> k >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        int l = 1, r = i; L[i] = i;
        while (l <= r)
        {
            memset(vs, 0, sizeof vs);
            for(int j = 1; j <= k; ++j) g[j].clear();
            int m = l+r>>1, ok = 1;
            for (int j = i; j > m; --j)
                if(j&1) g[a[j]].push_back(a[j-1]);
                else g[a[j-1]].push_back(a[j]);
            for (int j = i; ok && j > m; --j) if (!vs[a[j]] && cyclic(a[j])) ok = 0;

            if (ok) r = m - 1, L[i] = m;
            else l = m + 1;
        }
    }


    for (int x, y; q--;)
    {
        cin >> x >> y;
        if (x >= L[y]) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int cyclic(int)':
Main.cpp:19:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |         if (vs[v] == 1 || !vs[v] && cyclic(v)) return 1;
      |                           ~~~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:37:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |             int m = l+r>>1, ok = 1;
      |                     ~^~

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