oj.uz

Submission #933674

# Submission time Handle Problem Language Result Execution time Memory
933674 2024-02-26T04:56:41 Z 8pete8 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3496 ms 193024 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=3e5,lg=30,inf=1e18,minf=-1e18,Mxn=3725000,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,bruh=0;
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());
			if(st[i]+element[i].size()>Mxn)return;
			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)){
				bruh++;
				if(x==0)return;
				element[x-1].pb(y);
			}
			return;
		}
		for(;x<=n;x+=(x&-x)){
			if(x==0)return;
			int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
		//	k=min(k,st[x]-st[x-1]);
			while(k<=st[x]-st[x-1]){
				if(k==0)return;
				if(st[x-1]+k-1<0)return;
				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)return sum;
			int k=ub(e+st[x-1],e+st[x],y)-(e+st[x-1]);
	//		k=min(k,st[x]-st[x-1]);
			while(k){
				if(k==0)return sum;
				if(st[x-1]+k-1<0)return 0;
				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+1;
		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+1,r+=n+1;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(x>n)return 0;
			if(a[x]=='1'){
				int gl=getl(x),gr=getr(x);
				if(gl<=0||gr>n)return 0;
				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);
				if(gl<=0||gr>n)return 0;
				t.addrange(gl,gr,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(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: 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 2 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 48012 KB Output is correct
2 Correct 361 ms 48560 KB Output is correct
3 Correct 729 ms 59568 KB Output is correct
4 Correct 1853 ms 127728 KB Output is correct
5 Correct 1505 ms 107516 KB Output is correct
6 Correct 2146 ms 146356 KB Output is correct
7 Correct 99 ms 34240 KB Output is correct
8 Correct 111 ms 37536 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 5 ms 12892 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 3496 ms 191368 KB Output is correct
6 Correct 2487 ms 162956 KB Output is correct
7 Correct 1514 ms 107732 KB Output is correct
8 Correct 145 ms 36836 KB Output is correct
9 Correct 78 ms 21936 KB Output is correct
10 Correct 84 ms 30020 KB Output is correct
11 Correct 81 ms 30144 KB Output is correct
12 Correct 141 ms 34456 KB Output is correct
13 Correct 145 ms 37272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12788 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 203 ms 32604 KB Output is correct
6 Correct 1118 ms 93516 KB Output is correct
7 Correct 2184 ms 144388 KB Output is correct
8 Correct 3395 ms 193024 KB Output is correct
9 Correct 501 ms 77328 KB Output is correct
10 Correct 388 ms 71164 KB Output is correct
11 Correct 502 ms 77716 KB Output is correct
12 Correct 383 ms 70544 KB Output is correct
13 Correct 503 ms 81508 KB Output is correct
14 Correct 383 ms 70112 KB Output is correct
15 Correct 143 ms 35372 KB Output is correct
16 Correct 144 ms 36248 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 253 ms 48012 KB Output is correct
9 Correct 361 ms 48560 KB Output is correct
10 Correct 729 ms 59568 KB Output is correct
11 Correct 1853 ms 127728 KB Output is correct
12 Correct 1505 ms 107516 KB Output is correct
13 Correct 2146 ms 146356 KB Output is correct
14 Correct 99 ms 34240 KB Output is correct
15 Correct 111 ms 37536 KB Output is correct
16 Correct 5 ms 12888 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 4 ms 10844 KB Output is correct
19 Correct 3 ms 10588 KB Output is correct
20 Correct 3496 ms 191368 KB Output is correct
21 Correct 2487 ms 162956 KB Output is correct
22 Correct 1514 ms 107732 KB Output is correct
23 Correct 145 ms 36836 KB Output is correct
24 Correct 78 ms 21936 KB Output is correct
25 Correct 84 ms 30020 KB Output is correct
26 Correct 81 ms 30144 KB Output is correct
27 Correct 141 ms 34456 KB Output is correct
28 Correct 145 ms 37272 KB Output is correct
29 Correct 4 ms 12636 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 4 ms 12788 KB Output is correct
32 Correct 5 ms 12892 KB Output is correct
33 Correct 203 ms 32604 KB Output is correct
34 Correct 1118 ms 93516 KB Output is correct
35 Correct 2184 ms 144388 KB Output is correct
36 Correct 3395 ms 193024 KB Output is correct
37 Correct 501 ms 77328 KB Output is correct
38 Correct 388 ms 71164 KB Output is correct
39 Correct 502 ms 77716 KB Output is correct
40 Correct 383 ms 70544 KB Output is correct
41 Correct 503 ms 81508 KB Output is correct
42 Correct 383 ms 70112 KB Output is correct
43 Correct 143 ms 35372 KB Output is correct
44 Correct 144 ms 36248 KB Output is correct
45 Correct 91 ms 33164 KB Output is correct
46 Correct 166 ms 34732 KB Output is correct
47 Correct 875 ms 80640 KB Output is correct
48 Correct 1804 ms 135988 KB Output is correct
49 Correct 84 ms 29364 KB Output is correct
50 Correct 86 ms 29168 KB Output is correct
51 Correct 85 ms 29968 KB Output is correct
52 Correct 88 ms 30392 KB Output is correct
53 Correct 92 ms 29636 KB Output is correct
54 Correct 88 ms 30340 KB Output is correct