Submission #314831

#TimeUsernameProblemLanguageResultExecution timeMemory
314831AmineWeslatiStreet Lamps (APIO19_street_lamps)C++14
60 / 100
386 ms27124 KiB
//Never stop trying #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef string str; typedef long long ll; typedef double db; typedef long double ld; typedef pair<int, int> pi; #define fi first #define se second typedef vector<int> vi; typedef vector<pi> vpi; typedef vector<str> vs; typedef vector<ld> vd; #define pb push_back #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define endl "\n" #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) const int MOD = 1e9 + 7; //998244353 const ll INF = 1e18; const int MX = 3e5 + 10; const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up template<class T> using V = vector<T>; template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x)) #define dbg(x) cerr << " - " << #x << " : " << x << endl; #define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl; #define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl; void IO() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } int N,Q; str s; V<pair<int,pi>> q; bool sub2(){ for(auto x: q) if(x.fi==1){ if(x.se.se-x.se.fi!=1) return false; } return true; } bool sub3(){ str ss=s; for(auto x: q) if(x.fi==0){ int idx=x.se.fi; if(ss[idx]=='0') ss[idx]=1; else return false; } return true; } bool check(str ss, int l, int r){ FOR(i,l,r) if(ss[i]=='0') return 0; return 1; } V<ll> t(4*MX,INF); void update(int i, int x, int pos=1, int l=0, int r=N-1){ if(l==r){ t[pos]=x; return; } int m=(l+r)/2; if(i<=m) update(i,x,pos*2,l,m); else update(i,x,pos*2+1,m+1,r); t[pos]=max(t[pos*2],t[pos*2+1]); } ll get(int l, int r, int pos=1, int tl=0, int tr=N-1){ if(l>r) return -1; if(l==tl && r==tr) return t[pos]; int tm=(tl+tr)/2; return max(get(l,min(tm,r),pos*2,tl,tm),get(max(tm+1,l),r,pos*2+1,tm+1,tr)); } int main() { boost; cin>>N>>Q; cin>>s; FOR(i,0,Q){ str t; cin>>t; if(t=="toggle"){ int i; cin>>i; i--; q.pb({0,{i,-1}}); } else{ int i,j; cin>>i>>j; i--; j--; q.pb({1,{i,j}}); } } vi ans; if(N<=100 && Q<=100){ FOR(i,0,Q)if(q[i].fi==1){ str ss=s; int x=0; int l=q[i].se.fi,r=q[i].se.se; if(check(ss,l,r)) x++; FOR(j,0,i){ if(q[j].fi==0){ int idx=q[j].se.fi; if(ss[idx]=='0') ss[idx]='1'; else ss[idx]='0'; } if(check(ss,l,r)) x++; } ans.pb(x); } } else if(sub2()){ vi v(N,0),state(N,-1); FOR(j,0,N) if(s[j]=='1') state[j]=0; FOR(i,0,Q){ if(q[i].fi==0){ int idx=q[i].se.fi; if(state[idx]==-1) state[idx]=i+1; else{ v[idx]+=i+1-state[idx]; state[idx]=-1; } } else{ int idx=q[i].se.fi; ans.pb(v[idx]+(state[idx]!=-1)*(i+1-state[idx])); } } } else if(sub3()){ FOR(i,0,N)if(s[i]=='1') update(i,0); FOR(i,0,Q){ if(q[i].fi==0) update(q[i].se.fi,i+1); else{ int l=q[i].se.fi,r=q[i].se.se; ll x=get(l,r-1); ans.pb(max(0ll,i+1-x)); } } } for(auto x: ans) cout << x << endl; return 0; } /* Careful!!! .Array bounds .Infinite loops .Uninitialized variables / empty containers .Order of input Some insights: .Binary search .Graph representation .Write brute force code .Change your approach */

Compilation message (stderr)

street_lamps.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
street_lamps.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
street_lamps.cpp: In function 'void IO()':
street_lamps.cpp:49:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  freopen("input.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  freopen("output.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...