Submission #900520

#	Time	Username	Problem	Language	Result	Execution time	Memory
900520		vjudge1	Alternating Heights (CCO22_day1problem1)	C++17	17 / 25	1040 ms	13944 KiB

Main

#include <bits/stdc++.h>
#ifndef memset0
#define endl '\n'
#endif
using namespace std;
const int N = 3e3 + 9;
int n, k, q, a[N], ok[N], deg[N];
vector<int> G[N];
bool check(int l, int r) {
  // cerr << "check " << l << " " << r << endl;
  fill_n(deg + 1, n, 0);
  for (int i = 1; i <= n; i++) { G[i].clear(); }
  for (int i = l; i < r; i++) {
    int x = a[i], y = a[i + 1];
    if ((i - l) & 1) swap(x, y);
    G[x].push_back(y);
    deg[y]++;
    // cerr << x << "->" << y << endl;
  }
  static int q[N];
  l = 1, r = 0;
  for (int i = 1; i <= n; i++)
    if (!deg[i]) { q[++r] = i; }
  while (l <= r) {
    int u = q[l++];
    for (int v : G[u]) {
      --deg[v];
      if (!deg[v]) { q[++r] = v; }
    }
  }
  for (int i = 1; i <= n; i++)
    if (deg[i]) return false;
  return true;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> q;
  for (int i = 1; i <= n; i++) { cin >> a[i]; }
  for (int l, r, mid, i = 1; i <= n; i++) {
    ok[i] = i, l = i + 1, r = n;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (check(i, mid)) {
        ok[i] = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  for (int l, r, i = 1; i <= q; i++) {
    cin >> l >> r;
    cout << (r <= ok[l] ? "YES" : "NO") << endl;
  }
}

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