oj.uz

답안 #933654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933654 2024-02-26T04:08:22 Z 8pete8 가로등 (APIO19_street_lamps) C++17
20 / 100
 1157 ms 172916 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<int,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,{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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 5 ms 18780 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 6 ms 18780 KB Output is correct
6 Correct 6 ms 18780 KB Output is correct
7 Correct 4 ms 18780 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 76020 KB Output is correct
2 Correct 798 ms 66268 KB Output is correct
3 Correct 1157 ms 62860 KB Output is correct
4 Runtime error 694 ms 128172 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 5 ms 18968 KB Output is correct
5 Runtime error 1149 ms 172916 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 7 ms 19288 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 11 ms 19036 KB Output is correct
5 Correct 192 ms 28792 KB Output is correct
6 Runtime error 475 ms 98204 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 5 ms 18780 KB Output is correct
4 Correct 5 ms 18780 KB Output is correct
5 Correct 6 ms 18780 KB Output is correct
6 Correct 6 ms 18780 KB Output is correct
7 Correct 4 ms 18780 KB Output is correct
8 Correct 682 ms 76020 KB Output is correct
9 Correct 798 ms 66268 KB Output is correct
10 Correct 1157 ms 62860 KB Output is correct
11 Runtime error 694 ms 128172 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -