oj.uz

Submission #314973

# Submission time Handle Problem Language Result Execution time Memory
314973 2020-10-21T18:22:45 Z AmineWeslati Street Lamps (APIO19_street_lamps) C++14
80 / 100
 505 ms 46180 KB 
//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));
}


bool cmp(pair<pi,pi> a, pair<pi,pi> b){
	if(a.fi.fi!=b.fi.fi) return a.fi.fi < b.fi.fi;
	return a.se.se < b.se.se;
}

vi bit(MX,0);
void add(int i, int v){
	i++;
	for(;i<MX;i+=i&-i) bit[i]+=v;
}
int getSum(int i){
	int ans=0;
	for(;i;i-=i&-i) ans+=bit[i];
	return ans;
}
int getSumRange(int l, int r){
	l++; r++;
	return getSum(r)-getSum(l-1);
}

vi number(MX,0);
void updateNumber(int i,int v){
	i++;
	for(;i<MX;i+=i&-i) number[i]+=v;
}
int getNum(int i){
	int ans=0;
	for(;i;i-=i&-i) ans+=number[i];
	return ans;
}
int getNumber(int l, int r){
	r++; l++;
	return getNum(r)-getNum(l-1);
}


vi rmv(MX,0);
void updateToRemove(int i,int v){
	i++;
	for(;i<MX;i+=i&-i) rmv[i]+=v;
}
int getRmv(int i){
	int ans=0;
	
	for(;i;i-=i&-i) ans+=rmv[i];
	return ans;
}
int getToRemove(int l, int r){
	r++; l++;
	return getRmv(r)-getRmv(l-1);
}


vi closed(MX,0);
void updateClosed(int i,int v){
	i++;
	for(;i<MX;i+=i&-i) closed[i]+=v;
}
int getCl(int i){	
	int ans=0;
	for(;i;i-=i&-i) ans+=closed[i];
	return ans;
}
int getClosed(int l, int r){
	r++; l++;
	return getCl(r)-getCl(l-1);
}

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));
			}
		}
	}
	else{
		str ss=s;
		FOR(i,0,N) if(s[i]=='1') add(i,1);

		pi a[N]; //{right of the interval, moment it opened}
		FOR(i,0,N) a[i]={-1,-1}; 

		int cnt=0;
		FOR(i,0,sz(ss)){
			if(s[i]=='1') cnt++;
			if(s[i]=='0' || i==N-1){
				if(cnt>0){
					int x=(i==N-1 && s[i]=='1');
					int l=i-cnt+x,r=i-1+x;
					a[l]={r,0};
				}
				cnt=0;
			}
		}

		//FOR(i,0,N) cout << a[i].fi << ' ' << a[i].se << endl;

		V<pair<pi,int>> vec; //closed intervals and their duration
		int i=0; 

		for(;i<Q;i++){
			if(q[i].fi==1) break;
			int idx=q[i].se.fi;

			int l=idx,r=idx;
			int ll=0,rr=idx-1;
			while(ll<=rr){
				int m=(ll+rr)/2;
				if(getSumRange(m,idx-1)==idx-m){
					l=m; rr=m-1;
				}
				else ll=m+1;
			}

			ll=idx+1,rr=N-1;
			while(ll<=rr){
				int m=(ll+rr)/2;
				if(getSumRange(idx+1,m)==m-idx){
					r=m; ll=m+1;
				}
				else rr=m-1;
			}

			//cout << l << ' ' << r << endl;

			if(ss[idx]=='1'){ //111 1 111 --> 111 0 111
				vec.pb({{l,r},i+1-a[l].se});
				a[l]={-1,-1};
				if(l!=idx){
					a[l]={idx-1,i+1};
				}
				if(r!=idx){
					a[idx+1]={r,i+1};
				}

				add(idx,-1);
				ss[idx]='0';
			}
			else{ //111 0 111 --> 1111111
				if(l!=idx){
					vec.pb({{l,idx-1},i+1-a[l].se});
					a[l]={-1,-1};
				}
				if(r!=idx){
					vec.pb({{idx+1,r},i+1-a[idx+1].se});
					a[idx+1]={-1,-1};
				}
				a[l]={r,i+1};

				add(idx,1);
				ss[idx]='1';
			}
		}
		//for(auto x: vec) cout << x.fi.fi << ' ' << x.fi.se << ' ' << x.se << endl;
		//FOR(i,0,N) cout << a[i].fi << ' ' << a[i].se << endl;

		V<pair<pi,pi>> v; //closed intervals + opened intervals 
		                  //+ queries

		for(auto x: vec){
			v.pb({x.fi,{x.se,0}});
		}
		FOR(i,0,N) if(a[i].fi!=-1){
			v.pb({{i,a[i].fi},{a[i].se,1}});
		}
		for(;i<Q; i++){
			v.pb({{q[i].se.fi,q[i].se.se},{i,2}});
		}

		sort(all(v),cmp);

		/*for(auto x: v){
			cout << x.fi.fi << ' ' << x.fi.se << ' '
			<< x.se.fi << ' ' << x.se.se << endl;
		}*/

		vpi res; //{idx,ans};
		for(auto x: v){
			if(x.se.se==2){
				int idx=x.se.fi;
				int l=x.fi.fi,r=x.fi.se-1;
				//still open
				int val=(idx+1)*(getNumber(r,N-1)) - getToRemove(r,N-1); 
				//closed
				val+=getClosed(r,N-1);
				res.pb({idx,val});
			}
			else if(x.se.se==0){
				int r=x.fi.se; int val=x.se.fi;
				updateClosed(r,val);
			}
			else{
				int r=x.fi.se; int idx=x.se.fi;
				updateNumber(r,1);
				updateToRemove(r,idx);
			}
		}

		sort(all(res));
		for(auto x: res) ans.pb(x.se);
		
	}

	for(auto x: ans) cout << x << endl;


	return 0;
}

//35

/* 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

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 'int main()':
street_lamps.cpp:343:9: warning: unused variable 'l' [-Wunused-variable]
  343 |     int l=x.fi.fi,r=x.fi.se-1;
      |         ^
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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 20712 KB Output is correct
2 Correct 105 ms 21480 KB Output is correct
3 Correct 110 ms 21428 KB Output is correct
4 Correct 119 ms 23664 KB Output is correct
5 Correct 123 ms 24180 KB Output is correct
6 Correct 109 ms 23028 KB Output is correct
7 Correct 137 ms 25204 KB Output is correct
8 Correct 143 ms 26656 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 12 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 11 ms 14464 KB Output is correct
5 Correct 176 ms 21760 KB Output is correct
6 Correct 234 ms 21756 KB Output is correct
7 Correct 304 ms 21916 KB Output is correct
8 Correct 387 ms 24432 KB Output is correct
9 Correct 117 ms 20892 KB Output is correct
10 Correct 129 ms 22364 KB Output is correct
11 Correct 132 ms 22452 KB Output is correct
12 Correct 312 ms 22900 KB Output is correct
13 Correct 369 ms 24308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 271 ms 33396 KB Output is correct
6 Correct 340 ms 34808 KB Output is correct
7 Correct 409 ms 36344 KB Output is correct
8 Correct 505 ms 38672 KB Output is correct
9 Correct 225 ms 35676 KB Output is correct
10 Correct 193 ms 35548 KB Output is correct
11 Correct 229 ms 37244 KB Output is correct
12 Correct 193 ms 36340 KB Output is correct
13 Correct 227 ms 36444 KB Output is correct
14 Correct 196 ms 36420 KB Output is correct
15 Correct 318 ms 25716 KB Output is correct
16 Correct 374 ms 26612 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14464 KB Output is correct
7 Correct 10 ms 14464 KB Output is correct
8 Correct 100 ms 20712 KB Output is correct
9 Correct 105 ms 21480 KB Output is correct
10 Correct 110 ms 21428 KB Output is correct
11 Correct 119 ms 23664 KB Output is correct
12 Correct 123 ms 24180 KB Output is correct
13 Correct 109 ms 23028 KB Output is correct
14 Correct 137 ms 25204 KB Output is correct
15 Correct 143 ms 26656 KB Output is correct
16 Correct 10 ms 14464 KB Output is correct
17 Correct 12 ms 14464 KB Output is correct
18 Correct 10 ms 14464 KB Output is correct
19 Correct 11 ms 14464 KB Output is correct
20 Correct 176 ms 21760 KB Output is correct
21 Correct 234 ms 21756 KB Output is correct
22 Correct 304 ms 21916 KB Output is correct
23 Correct 387 ms 24432 KB Output is correct
24 Correct 117 ms 20892 KB Output is correct
25 Correct 129 ms 22364 KB Output is correct
26 Correct 132 ms 22452 KB Output is correct
27 Correct 312 ms 22900 KB Output is correct
28 Correct 369 ms 24308 KB Output is correct
29 Correct 10 ms 14464 KB Output is correct
30 Correct 10 ms 14464 KB Output is correct
31 Correct 10 ms 14464 KB Output is correct
32 Correct 10 ms 14464 KB Output is correct
33 Correct 271 ms 33396 KB Output is correct
34 Correct 340 ms 34808 KB Output is correct
35 Correct 409 ms 36344 KB Output is correct
36 Correct 505 ms 38672 KB Output is correct
37 Correct 225 ms 35676 KB Output is correct
38 Correct 193 ms 35548 KB Output is correct
39 Correct 229 ms 37244 KB Output is correct
40 Correct 193 ms 36340 KB Output is correct
41 Correct 227 ms 36444 KB Output is correct
42 Correct 196 ms 36420 KB Output is correct
43 Correct 318 ms 25716 KB Output is correct
44 Correct 374 ms 26612 KB Output is correct
45 Runtime error 109 ms 46180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -