제출 #883770

#제출 시각아이디문제언어결과실행 시간메모리
883770noiaintAlternating Heights (CCO22_day1problem1)C++17
25 / 25
213 ms42832 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #define file "" #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int mod = (int)1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int oo = 1e9; const long long ooo = 1e18; template<class X, class Y> bool mini(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maxi(X &a, Y b) { return a < b ? (a = b, true) : false; } void add(int &a, int b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int n, k, q; int a[N]; vector<int> adj[N]; int color[N]; int res[N]; bool ok = true; void dfs(int u) { color[u] = 1; for (int v : adj[u]) { if (!color[v]) dfs(v); else if (color[v] == 1) { ok = false; return; } } color[u] = 2; } bool no_cycle(int l, int r) { for (int i = 1; i <= k; ++i) { adj[i].clear(); color[i] = 0; } vector<int> val; for (int i = l; i <= r; ++i) { if (i + 1 <= r && a[i] == a[i + 1]) return false; val.push_back(a[i]); } // edge x->y : x > y for (int i = 0; i + 1 < r - l + 1; ++i) { int x = val[i], y = val[i + 1]; if (i & 1) adj[y].push_back(x); else adj[x].push_back(y); } for (int i = 1; i <= k; ++i) if (adj[i].size() && color[i] == 0) { ok = true; dfs(i); if (ok == false) return false; } return true; } void process() { cin >> n >> k >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; int r = 1; for (int l = 1; l <= n; ++l) { while (r <= n && no_cycle(l, r)) ++r; res[l] = r; // cout << res[l] << ' '; } while (q--) { int l, r; cin >> l >> r; cout << (res[l] > r ? "YES" : "NO") << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #else // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); #endif int tc = 1; // cin >> tc; while (tc--) { process(); } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...