oj.uz

Submission #933657

# Submission time Handle Problem Language Result Execution time Memory
933657 2024-02-26T04:13:22 Z 8pete8 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1160 ms 177008 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
//#define int long long
const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}	 
int active=0;
int n,q;
struct fen2d{
/*
	l, add at l, stop at x+1
	r add at x,stop at r+1
	l,t x+1,-t
	x,t r+1,-t
	first{
		update(l,x,t)
		update(l,r+1,-t)
		update(x+1,x,-t)
		update(x+1,r+1,t)
	}*/
	vector<int>element[mxn+10];
	int e[mxn+10],st[mxn+10],fwk[mxn+10];
	int cnt=0;
	void init(){
		int m=0;
		active=1;
		for(int i=0;i<mxn;i++){
			st[i]=m;
			sort(all(element[i]));
			element[i].erase(unique(all(element[i])),element[i].end());
			copy(all(element[i]),e+st[i]);
			m+=element[i].size();
		}
		st[n]=m;
	}
	void update(int x,int y,int val){ 
		if(!active){
			for(;x<=mxn;x+=(x&-x)){
			//	if(x==0)assert(0);
				element[x-1].pb(y);
			}
			return;
		}
		for(;x<=mxn;x+=(x&-x)){
			if(x==0)assert(0);
			int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
			while(k<=st[x]-st[x-1]){
				fwk[st[x-1]+k-1]+=val;
				k+=(k&-k);
			}
		}
	}
	int qry(int x,int y){
		int sum=0;
		for(;x>0;x-=(x&-x)){
			//if(x==0)assert(0);
			int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
			while(k){
				sum+=fwk[st[x-1]+k-1];
				k-=(k&-k);
			}
		}
		return sum;
	}
	void addrange(int l,int r,int x,int val){
		update(l,x,val);
		update(l,r+1,-val);
		update(x+1,x,-val);
		update(x+1,r+1,val);
	}
}t;
struct seg{
	int v[2*mxn+10];
	void update(int pos,int val){
		pos+=n;
		v[pos]=val;
		for(int i=pos;i>0;i>>=1)v[i>>1]=(v[i]&v[i^1]);
	}
	int qry(int l,int r){
		int ans=1;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)ans=(ans&v[l++]);
			if(!(r&1))ans=(ans&v[r--]);
		}
		return ans;
	}
}t2;
int getl(int x){
	int l=1,r=x;
	int ans=x;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(t2.qry(mid,x))r=mid-1,ans=min(ans,mid);
		else l=mid+1;
	}
	return ans;
}
int getr(int x){
	int l=x,r=n;
	int ans=x;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(t2.qry(x,mid))l=mid+1,ans=max(ans,mid);
		else r=mid-1;
	}
	return ans;
}
int32_t main(){
	fastio
	cin>>n>>q;
	string a;cin>>a;
	a='b'+a;
	string keep=a;
	for(int i=1;i<=n;i++)if(a[i]=='1')t2.update(i,1);
	vector<pair<pii,pii>>qry;
	for(int i=0;i<q;i++){
		string ty;cin>>ty;
		if(ty=="query"){
			int l,r;cin>>l>>r;
			r--;
			qry.pb({{1,0},{l,r}});
		}
		else{
			int x;cin>>x;
			if(a[x]=='1'){
				int gl=getl(x),gr=getr(x);
				t.addrange(gl,gr,x,0);
				qry.pb({{2,x},{gl,gr}});
				a[x]='0';
				t2.update(x,0);
			}
			else{
				a[x]='1';
				t2.update(x,1);
				int gl=getl(x),gr=getr(x);
				t.addrange(gl,getr(x),x,0);
				qry.pb({{2,x},{gl,gr}});
			}
		}
	}
	for(int i=1;i<=n;i++)t2.update(i,(keep[i]=='1'));
	t.init();
	a=keep;
	for(int i=0;i<q;i++){
		if(qry[i].f.f==1){
			int ans=t.qry(qry[i].s.f,qry[i].s.s);
			if(t2.qry(qry[i].s.f,qry[i].s.s))ans+=(i+1);
			cout<<ans<<'\n';
		}
		else{
			int x=qry[i].f.s;
			if(a[x]=='1'){
				t.addrange(qry[i].s.f,qry[i].s.s,x,i+1);
				a[x]='0';
				t2.update(x,0);
			}
			else{
				a[x]='1';
				t2.update(x,1);
				//cout<<qry[i].s.f<<" "<<getl(x)<<" "<<qry[i].s.s<<" "<<getr(x)<<'\n';
				t.addrange(qry[i].s.f,qry[i].s.s,x,-i-1);
			}
		}
	}
	/*

	qry l->r

	turn on at x ->lf,ri of continuos segment then every lf<=l<=x,x<=r<=ri will start -> -t
	turn of at x->lf,ri of contiuos segment then every lf<=l<=x,x<=r<=ri will end -> +t
	qry l,r->if l,r still on then ans=l,r+t->to end else ans=l,r

	update can be done by 2d offline fenwick
	->sort all l,r
	each l is first dimension
	second dimension is different for each l


	finding lf and ri can be dones by bnary search and seg tree?

	*/
}

Compilation message

street_lamps.cpp:34:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   34 | const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
      |                                       ^~~~
street_lamps.cpp:34:49: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   34 | const int mod=1e9+7,mxn=5e5,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
      |                                                 ^~~~~
street_lamps.cpp: In function 'void setIO(std::string)':
street_lamps.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18780 KB Output is correct
2 Correct 4 ms 18868 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 4 ms 18776 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 5 ms 18932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 84120 KB Output is correct
2 Correct 747 ms 81280 KB Output is correct
3 Correct 995 ms 68780 KB Output is correct
4 Runtime error 705 ms 132096 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19288 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 5 ms 18868 KB Output is correct
5 Runtime error 1160 ms 177008 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 6 ms 19032 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 10 ms 19080 KB Output is correct
5 Correct 192 ms 29076 KB Output is correct
6 Runtime error 502 ms 102728 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18780 KB Output is correct
2 Correct 4 ms 18868 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 4 ms 18776 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 5 ms 18932 KB Output is correct
8 Correct 613 ms 84120 KB Output is correct
9 Correct 747 ms 81280 KB Output is correct
10 Correct 995 ms 68780 KB Output is correct
11 Runtime error 705 ms 132096 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -