oj.uz

Submission #933652

# Submission time Handle Problem Language Result Execution time Memory
933652 2024-02-26T04:05:18 Z 8pete8 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1150 ms 169696 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<n;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<=n;x+=(x&-x)){
				if(x==0)assert(0);
				element[x-1].pb(y);
			}
			return;
		}
		for(;x<=n;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<int,pii>>qry;
	for(int i=0;i<q;i++){
		string ty;cin>>ty;
		if(ty=="query"){
			int l,r;cin>>l>>r;
			r--;
			r=max(r,l);
			qry.pb({1,{l,r}});
		}
		else{
			int x;cin>>x;
			qry.pb({2,{x,-1}});
			if(a[x]=='1'){
				t.addrange(getl(x),getr(x),x,0);
				a[x]='0';
				t2.update(x,0);
			}
			else{
				a[x]='1';
				t2.update(x,1);
				t.addrange(getl(x),getr(x),x,0);
			}
		}
	}
	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==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].s.f;
			if(a[x]=='1'){
				t.addrange(getl(x),getr(x),x,i+1);
				a[x]='0';
				t2.update(x,0);
			}
			else{
				a[x]='1';
				t2.update(x,1);
				t.addrange(getl(x),getr(x),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 4 ms 16732 KB Output is correct
2 Correct 3 ms 18924 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 32476 KB Output is correct
2 Correct 351 ms 34380 KB Output is correct
3 Correct 706 ms 40440 KB Output is correct
4 Runtime error 692 ms 126504 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 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 16980 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Runtime error 1150 ms 169696 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 4 ms 18780 KB Output is correct
2 Correct 5 ms 18780 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 6 ms 19036 KB Output is correct
5 Correct 193 ms 27864 KB Output is correct
6 Runtime error 476 ms 99028 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 4 ms 16732 KB Output is correct
2 Correct 3 ms 18924 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 235 ms 32476 KB Output is correct
9 Correct 351 ms 34380 KB Output is correct
10 Correct 706 ms 40440 KB Output is correct
11 Runtime error 692 ms 126504 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -