제출 #1167052

#제출 시각아이디문제언어결과실행 시간메모리
1167052WH8Alternating Heights (CCO22_day1problem1)C++20
0 / 25
1002 ms3836 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define mp make_pair #define pb push_back #define int long long #define f first #define s second #define pll pair<long long, long long> struct SparseTable{ vector<vector<int>> st; int n, max_log; int log2_floor(unsigned long long i) { return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1; } void initialize(const vector<int>& v) { n = v.size(); max_log = log2_floor(n) + 1; st.assign(max_log, vector<int>(n)); // Initialize the first row of the sparse table for (int i = 0; i < n; i++) { st[0][i] = v[i]; } // Fill the sparse table for (int i = 1; i < max_log; i++) { for (int j = 0; j + (1 << i) <= n; j++) { st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } } int query(int a, int b) { int i = log2_floor(b - a + 1); return min(st[i][a], st[i][b - (1 << i) + 1]); } }; vector<pair<int,int>> cy; int n,k,q; int a[3005]; vector<vector<pll>> al(3005); vector<pll> ps; int col[3005]; void dfs(int x){ for(auto [it, ind] :al[x]){ if(col[it]==2)continue; if(col[it]==1){ bool found=false; int mn=ind, mx=ind; //~ printf("cycle towards %lld, edge ind %lld\n",it,ind); for(int j=ps.size()-1; j>=0;j--){ if(ps[j].f==it){ found=true; break; } mn=min(mn,ps[j].s); mx=max(mx,ps[j].s); } assert(found); cy.pb({mn, mx}); } if(col[it]==0){ col[it]=1; ps.pb({it, ind}); dfs(it); } } ps.pop_back(); col[x]=2; } signed main(){ cin>>n>>k>>q; for(int i=0;i<n;i++){ cin>>a[i]; if(i>=1){ if(i%2==1)al[a[i-1]].pb({a[i], i+1}); else al[a[i]].pb({a[i-1], i+1}); } } col[1]=1; for(int i=1;i<=k;i++){ if(col[i]==2)continue; col[i]=1; ps.clear(); ps.pb({i, -1}); dfs(i); } //~ for(auto it:cy){ //~ cout<<it.f<<" "<<it.s<<"|"; //~ } sort(cy.begin(),cy.end()); vector<int> stv; for(auto it:cy){ stv.pb(it.s); } SparseTable st; st.initialize(stv); for(int i=0;i<q;i++){ int l,r;cin>>l>>r; l++; int lb=lower_bound(cy.begin(),cy.end(),mp(l,(int)-1))-cy.begin(); int rb=upper_bound(cy.begin(),cy.end(),mp(r,(int)1e15))-cy.begin()-1; if(rb<lb){ cout<<"YES\n"; continue; } int mn=st.query(lb, rb); if(mn<=r)cout<<"NO\n"; else cout<<"YES\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...