제출 #971372

#제출 시각아이디문제언어결과실행 시간메모리
971372KiaRezAlternating Heights (CCO22_day1problem1)C++17
25 / 25
275 ms24276 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 18; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, k, q, a[N], deg[N], ptr, res[N]; vector<int> adj[N]; bool check(int x, int y) { int wh = 0; for(int i=x; i<y; i++) { if(wh == 0) deg[a[i]]++, adj[a[i+1]].pb(a[i]); else deg[a[i+1]]++, adj[a[i]].pb(a[i+1]); wh^=1; } queue<int> qu; for(int i=1; i<=k; i++) if(deg[i] == 0) qu.push(i); int cnt = 0; while(size(qu) > 0) { int v = qu.front(); qu.pop(); cnt++; for(auto it : adj[v]) { deg[it] --; if(deg[it] == 0) qu.push(it); } } for(int i=1; i<=k; i++) { deg[i]=0; adj[i].clear(); } return (cnt == k); } int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n>>k>>q; for(int i=1; i<=n; i++) cin>>a[i]; ptr=1; for(int i=1; i<=n; i++) { while(check(ptr, i) == 0) ptr++; res[i] = ptr; } while(q--) { int x,y; cin>>x>>y; if(res[y] <= x) cout<<"YES\n"; else cout<<"NO\n"; } 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...