Submission #1124844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124844		duckindog	Alternating Heights (CCO22_day1problem1)	C++20	11 / 25	1096 ms	4584 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];
bool pass;
int cnt[N];
void dfs(int u) { 
  for (const auto& v : ad[u]) { 
    cnt[v] += 1;
    if (cnt[v] >= 2) pass = true;
    if (!pass) dfs(v);
    cnt[v] -= 1;
  }
}

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]);
    }
    
    pass = false;
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= k; ++i) { 
      cnt[i] += 1;
      dfs(i);
      cnt[i] -= 1;
    }

    return !pass;
  };

  int it = 1;
  for (int i = 1; i <= n; ++i) { 
    while (it <= n && chk(i, it)) it += 1;
    longest[i] = it - 1;
  }

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

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

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