답안 #933675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933675 2024-02-26T04:58:48 Z 8pete8 가로등 (APIO19_street_lamps) C++17
20 / 100
2616 ms 189428 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=4e6,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());
			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)){
				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]);
			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]);
			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}});
			}
		}
	}
	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';
			}
			else{
				a[x]='1';
				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: 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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 235 ms 48048 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 193 ms 33352 KB Output is correct
6 Correct 915 ms 94604 KB Output is correct
7 Correct 1695 ms 144064 KB Output is correct
8 Correct 2616 ms 189428 KB Output is correct
9 Correct 426 ms 77472 KB Output is correct
10 Correct 342 ms 68364 KB Output is correct
11 Correct 425 ms 74836 KB Output is correct
12 Correct 339 ms 69104 KB Output is correct
13 Correct 430 ms 76564 KB Output is correct
14 Correct 346 ms 67856 KB Output is correct
15 Correct 127 ms 26644 KB Output is correct
16 Correct 137 ms 32404 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -