제출 #954004

#제출 시각아이디문제언어결과실행 시간메모리
954004thiago_bastosAlternating Heights (CCO22_day1problem1)C++17
25 / 25
949 ms14420 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e3 + 10; int n, k, q, a[N], last[N], deg[N]; vector<int> adj[N]; bool is_dag(int l, int r) { queue<int> q; int count = 0; for(int i = 0; i < n; ++i) { deg[i] = 0; adj[i].clear(); } for(int i = l + 1; i <= r; ++i) { if((i - l) % 2) { ++deg[a[i - 1]]; adj[a[i]].push_back(a[i - 1]); } else { ++deg[a[i]]; adj[a[i - 1]].push_back(a[i]); } } for(int i = 0; i < n; ++i) { if(!deg[i]) { if(adj[i].size()) q.push(i); } else ++count; } while(!q.empty()) { int u = q.front(); q.pop(); for(int v : adj[u]) { if(--deg[v] == 0) { --count; q.push(v); } } } return count == 0; } void solve() { cin >> n >> k >> q; for(int i = 0; i < n; ++i) {cin >> a[i]; --a[i];} for(int i = 0; i < n; ++i) { int lo = i, hi = n; while(lo < hi) { int mid = (lo + hi) / 2; if(!is_dag(i, mid)) hi = mid; else lo = mid + 1; } last[i] = hi - 1; } while(q--) { int l, r; cin >> l >> r; --l, --r; cout << (last[l] >= r ? "YES\n" : "NO\n"); } } int main() { int t = 1; ios_base :: sync_with_stdio(false); cin.tie(0); //cin >> t; while(t--) solve(); 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...