Submission #753696

#TimeUsernameProblemLanguageResultExecution timeMemory
753696epicci23Alternating Heights (CCO22_day1problem1)C++17
0 / 25
610 ms12764 KiB
#include "bits/stdc++.h" #pragma optimize ("Bismillahirrahmanirrahim") using namespace std; #define pb push_back #define ff first #define ss second #define endl "\n" #define int long long #define double long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define what_is(x) cerr << #x << " is " << x << endl; //#define m (l+r)/2 constexpr int N=200005; constexpr int MOD=1000000007; constexpr int INF2 = LLONG_MAX; constexpr int INF=(int)1e18; constexpr int LOG=30; typedef pair<int,int> pii; typedef tuple<int,int,int> tp; typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq; typedef priority_queue<pii> max_pq; typedef long long ll; //to think// /* * graph approach * dp * dividing the problem to smaller statements * finding the real constraint * sqrt decomposition * greedy approach * pigeonhole principle * rewriting the problem/equality * bitwise approaches * binary search if monotonic * divide and conquer * combinatorics * inclusion - exclusion * think like bfs */ inline int in() { int x;cin >> x; return x; } inline string in2() { string x;cin >> x; return x; } vector<int> v[3003]; int col[3003]; bool ok=0; void dfs(int c) { if(ok) return; if(col[c]==1) {ok=1;return;} if(col[c]==2) return; col[c]=1; for(int x:v[c]) dfs(x); col[c]=2; } void solve() { int n=in(),k=in(),q=in(); int ar[n+1]; for(int i=1;i<=n;i++) ar[i]=in(); int xd[n+1]; for(int i=1;i<=n;i++) { int l=i,r=n; while(l<r) { int mid=(l+r)/2; ok=0; for(int j=1;j<=k;j++) col[j]=0; for(int j=1;j<=k;j++) v[j].clear(); for(int j=i;j<mid;j++) { if((j-i)&1) v[ar[j+1]].pb(ar[j]); else v[ar[j]].pb(ar[j+1]); } for(int j=1;j<=k;j++) dfs(j); if(ok) r=mid; else l=mid+1; } xd[i]=l; } for(int i=1;i<=q;i++) { int u=in(),v=in(); if(xd[u]<=v) cout << "NO\n"; else cout << "YES\n"; } } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); int t=1;//cin>> t; for(int i=1;i<=t;i++) { // cout << "Case #" << i << ": "; solve(); } return 0; }

Compilation message (stderr)

Main.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("Bismillahirrahmanirrahim")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...