Submission #300073

#TimeUsernameProblemLanguageResultExecution timeMemory
300073mohamedsobhi777Street Lamps (APIO19_street_lamps)C++14
0 / 100
5035 ms5120 KiB
#include<bits/stdc++.h> /* #pragma GCC optimize("-Ofast") //#pragma GCC optimize("trapv") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-funroll-loops")*/ #define I inline void #define S struct #define vi vector<int> #define vii vector<pair<int,int>> #define pii pair<int,int> #define pll pair<ll,ll> using namespace std ; using ll = long long ; using ld = long double ; const int N = 1e5 + 7 , mod = 1e9 + 7 ; const int inf = N ; // How interesting! int n , k ; string s; int a[N] ; string tmp[N] ; int ts ; int solve(int l , int r){ int ret = 0 ; int x = r - l + 1; for(int i = 0 ;i <= ts ; i ++){ // cout<< tmp[i] <<" " ; ret+= (tmp[i].substr(l , x) == string(x , '1') ) ; } // cout<<"-----\n" ; //if(ts) // exit(0) ; return ret ; } int bit[N] ; I add(int pos, int x){ for(pos++ ;pos<N;pos+=pos&-pos) bit[pos]+=x ; } int upto(int x){ x++ ; int ret = 0 ; for(;x;x-=x&-x) ret+=bit[x] ; return ret ; } int get(int l, int r){ return upto(r) - upto(l - 1) ; } int solve2(int l ,int r){ int ret = 0 ; for(int i = 0 ;i <= ts ;i++){ // memset(bit , 0 , sizeof bit) ; vector<int> cont(n+1 , 0) , cont2(n+1 , 0); vector<pair<int,int>>v ; int cnt = 0 ; if(l == r){ ret += 2 * (tmp[i][l] -'0') ; continue; } for(int j = 0 ;j < n ;j ++){ if(tmp[i][j] == '1'){ if(cnt){ } else{ cont[j]++ ; } cnt++ ; }else{ if(cnt){ v.push_back({ j - cnt , j -1 }) ; cont[j-1]-- ; cont2[j-1] ++ ; }else{ } cnt = 0 ; } } if(cnt){ v.push_back({n - cnt , n - 1 }) ; cont[n-1] -- ; cont2[n-1] ++ ; } for(int j = 0 ;j <= l ;j ++){ ret += cont[j] ; } for(int j = r ; j < n ;j ++) ret -= cont[j] ; int aux = 0 ; for(int j = 0 ;j <= l ;j ++) aux += cont[j] ; for(int j = l + 1 ;j < r ; j ++) aux += cont2[j] ; aux /= 2; int q = 0 ; ret -= aux ; for(auto u : v){ if(u.first > l && u.second < r) continue ; if(u.first > l && u.first < r) ret -- ; if(u.second > l && u.second < r) q ++ ; } } return ret / 2; } int main(){ ios_base::sync_with_stdio(0) ; cin.tie(0) ; //freopen("in.in" , "r" , stdin) ; cin >> n >> k ; cin >> s ; tmp[0] = s; for(int i = 0 ;i < n;i ++) a[i] = s[i] - '0' ; for(int i = 0 ;i < k ;i ++){ string t ; int l , r; cin >> t ; if(t == "toggle"){ cin >> l ; tmp[ts+1] = tmp[ts] ;ts++; tmp[ts][l-1] = '1' - tmp[ts][l-1] + '0'; a[l] ^=1 ; } else{ cin >> l >> r; l-- ; r-=2; cout<< solve2(l , r) <<"\n"; tmp[ts + 1] = tmp[ts] ; ts ++ ; } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...