Submission #1124842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124842		duckindog	Alternating Heights (CCO22_day1problem1)	C++20	10 / 25	1012 ms	4568 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;

const int N = 3000 + 10;
int n, k, q;
int a[N];

vector<int> ad[N];
int low[N], num[N], it;
int scc[N], sccIt;
stack<int> st;
void dfs(int u, int p = -1) { 
  low[u] = num[u] = ++it;
  st.push(u);
  for (const auto& v : ad[u]) { 
    if (v == u) sccIt = k + 1;
    if (scc[v]) continue;
    if (num[v]) low[u] = min(low[u], num[v]);
    else { 
      dfs(v, u);
      low[u] = min(low[u], low[v]);
    }
  }

  if (low[u] == num[u]) { 
    sccIt += 1;
    for (;;) { 
      int x = st.top(); st.pop();
      scc[x] = sccIt;
      if (x == u) break;
    }
  }
}

int longest[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i];

  auto chk = [&](int l, int r) {     
    for (int i = 1; i <= k; ++i) ad[i].clear();
    for (int i = l + 1; i <= r; ++i) { 
      if ((l - i) & 1) ad[a[i - 1]].push_back(a[i]);
      else ad[a[i]].push_back(a[i - 1]);
    }

    memset(low, 0, sizeof low);
    memset(num, 0, sizeof num);
    memset(scc, 0, sizeof scc);
    it = sccIt = 0;
    
    for (int i = 1; i <= k; ++i) if (!num[i]) dfs(i);

    return sccIt == k;
  };

  for (int i = 1; i <= n; ++i) { 
    auto& ret = longest[i];
    int le = i, ri = n;

    while (le <= ri) { 
      int mid = (le + ri) >> 1;
      if (chk(i, mid)) le = (ret = mid) + 1;
      else ri = mid - 1;
    }
  }

  while (q--) { 
    int l, r; cin >> l >> r;

    cout << (longest[l] >= r ? "YES" : "NO") << "\n";
  }
}

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