답안 #197912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197912 2020-01-24T07:25:15 Z TAISA_ 가로등 (APIO19_street_lamps) C++14
100 / 100
2948 ms 269288 KB
#include <bits/stdc++.h>
#define mp make_pair
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
struct BIT{
	vector<int> dat;
	void build(int n){
		dat.resize(n+1,0);
	}
	void add(int k,int x){
		for(++k;k<dat.size();k+=k&-k){
			dat[k]+=x;
		}
	}
	int get(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=dat[k];
		}
		return res;
	}
};
struct Segtree{
	int n;
	vector<BIT> dat;
	vector<vector<int>> ds,ls,rs;
	Segtree(int n_){
		n=1;
		while(n<n_)n<<=1;
		ds.resize(2*n);
		ls.resize(2*n);
		rs.resize(2*n);
		dat.resize(2*n);
	}
	void preupd(int x,int y){
		ds[x+n].push_back(y);
	}
	void build(){
		for(int k=2*n-1;k>=n;k--){
			sort(all(ds[k]));
			ds[k].erase(unique(all(ds[k])),ds[k].end());
		}
		for(int k=n-1;k>0;k--){
			ds[k].resize(ds[k<<1].size()+ds[k<<1|1].size());
			merge(all(ds[k<<1]),all(ds[k<<1|1]),ds[k].begin());
			ds[k].erase(unique(all(ds[k])),ds[k].end());
			ls[k].resize(ds[k].size()+1);
			rs[k].resize(ds[k].size()+1);
			int t1=0,t2=0;
			for(int i=0;i<ds[k].size();i++){
				while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
				while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
				ls[k][i]=t1;
				rs[k][i]=t2;
			}
			ls[k][ds[k].size()]=ds[k<<1].size();
			rs[k][ds[k].size()]=ds[k<<1|1].size();
		}
		for(int k=0;k<2*n-1;k++){
			dat[k].build(ds[k].size());
		}
	}
	void upd(int x,int y,int z){
		int k=x+n;
		int yy=lower_bound(all(ds[k]),y)-ds[k].begin();
		dat[k].add(yy,z);
		k>>=1;
		while(k>0){
			yy=lower_bound(all(ds[k]),y)-ds[k].begin();
			dat[k].add(yy,z);
			k>>=1;
		}
	}
	int get(int a,int b,int x,int y,int k,int l,int r){
		if(b<=l||r<=a){
			return 0;
		}
		if(a<=l&&r<=b){
			return dat[k].get(y-1)-dat[k].get(x-1);
		}
		return get(a,b,ls[k][x],ls[k][y],k<<1,l,(l+r)>>1)+
				get(a,b,rs[k][x],rs[k][y],k<<1|1,(l+r)>>1,r);
	}
	inline int get(int a,int b,int x,int y){
		x=lower_bound(all(ds[1]),x)-ds[1].begin();
		y=lower_bound(all(ds[1]),y)-ds[1].begin();
		return get(a,b,x,y,1,0,n);
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;cin>>n>>q;
	string str;cin>>str;
	int b=-1;
	Segtree seg(n+10);
	set<pair<P,int>> st;
	vector<P> vi;
	for(int i=0;i<n;i++){
		if(str[i]=='1'){
			if(b==-1){
				b=i;
			}
		}else{
			if(b!=-1){
				st.insert(mp(P(b,i-1),-1));
				seg.preupd(b,i-1);
				b=-1;
			}
		}
	}
	if(b!=-1){
		st.insert(mp(P(b,n-1),-1));
		seg.preupd(b,n-1);
	}
	vector<vector<pair<P,int>>> vs(q);
	vector<int> res(q),aa(q,-1),bb(q);
	for(int i=0;i<q;i++){
		string t;cin>>t;
		if(t=="toggle"){
			int a;cin>>a;--a;
			auto add=[&](pair<P,int> p){
				st.erase(p);
				seg.preupd(p.first.first,p.first.second);
				vs[i].emplace_back(p.first,p.second);
			};
			auto ins=[&](pair<P,int> p){
				if(p.first.first<=p.first.second){
					st.insert(p);
				}
			};
			if(str[a]=='0'){
				str[a]='1';
				pair<P,int> to=mp(P(a,a),i);
				if(st.empty()){
					ins(to);
					continue;
				}
				auto ir=st.lower_bound(to);
				if(ir!=st.end()&&(*ir).first.first==a+1){
					to.first.second=(*ir).first.second;
					add(*ir);
				}
				auto il=st.lower_bound(to);
				if(il!=st.begin()){
					--il;
					if((*il).first.second==a-1){
						to.first.first=(*il).first.first;
						add(*il);
					}
				}
				ins(to);
			}else{
				str[a]='0';
				auto it=prev(st.lower_bound(mp(P(a+1,-1),-1)));
				pair<P,int> p=(*it);
				add(*it);
				ins(mp(P(p.first.first,a-1),i));
				ins(mp(P(a+1,p.first.second),i));
			}
		}else{
			int a;cin>>a>>b;--a;--b;--b;
			aa[i]=a,bb[i]=b;
			seg.preupd(0,a+1);
			seg.preupd(b,n);
			auto it=st.lower_bound(mp(P(a+1,-1),-1));
			if(!st.empty()&&it!=st.begin()){
				--it;
				if((*it).first.first<=a&&b<=(*it).first.second){
					res[i]+=i-(*it).second;
				}
			}
		}	
	}
	seg.build();
	for(int i=0;i<q;i++){
		if(aa[i]==-1){
			for(auto &e:vs[i]){
		//		cout<<e.first.first<<" "<<e.first.second<<" "<<i-e.second<<endl;
				seg.upd(e.first.first,e.first.second,i-e.second);
			}
		}else{
			res[i]+=seg.get(0,aa[i]+1,bb[i],n);
			//cout<<0<<" "<<aa[i]<<" "<<bb[i]<<" "<<n-1<<" "<<seg.get(0,aa[i]+1,bb[i],n)<<endl;
			cout<<res[i]<<'\n';
		}
	}	
}

Compilation message

street_lamps.cpp: In member function 'void BIT::add(int, int)':
street_lamps.cpp:14:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(++k;k<dat.size();k+=k&-k){
           ~^~~~~~~~~~~
street_lamps.cpp: In member function 'void Segtree::build()':
street_lamps.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<ds[k].size();i++){
                ~^~~~~~~~~~~~~
street_lamps.cpp:54:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(t1<ds[k<<1].size()&&ds[k<<1][t1]<ds[k][i])++t1;
           ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(t2<ds[k<<1|1].size()&&ds[k<<1|1][t2]<ds[k][i])++t2;
           ~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 21452 KB Output is correct
2 Correct 326 ms 22040 KB Output is correct
3 Correct 623 ms 27628 KB Output is correct
4 Correct 2682 ms 265968 KB Output is correct
5 Correct 2805 ms 267124 KB Output is correct
6 Correct 2836 ms 263424 KB Output is correct
7 Correct 1273 ms 255168 KB Output is correct
8 Correct 1255 ms 256620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 1 ms 888 KB Output is correct
5 Correct 2666 ms 240628 KB Output is correct
6 Correct 2887 ms 259676 KB Output is correct
7 Correct 2655 ms 262532 KB Output is correct
8 Correct 1357 ms 249228 KB Output is correct
9 Correct 140 ms 14860 KB Output is correct
10 Correct 151 ms 16508 KB Output is correct
11 Correct 155 ms 16364 KB Output is correct
12 Correct 1208 ms 247604 KB Output is correct
13 Correct 1210 ms 249392 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 888 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 1867 ms 269288 KB Output is correct
6 Correct 2130 ms 265752 KB Output is correct
7 Correct 2451 ms 260768 KB Output is correct
8 Correct 2948 ms 245192 KB Output is correct
9 Correct 353 ms 22912 KB Output is correct
10 Correct 270 ms 23672 KB Output is correct
11 Correct 348 ms 22840 KB Output is correct
12 Correct 272 ms 23672 KB Output is correct
13 Correct 348 ms 22772 KB Output is correct
14 Correct 278 ms 23672 KB Output is correct
15 Correct 1230 ms 247752 KB Output is correct
16 Correct 1224 ms 249216 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 269 ms 21452 KB Output is correct
9 Correct 326 ms 22040 KB Output is correct
10 Correct 623 ms 27628 KB Output is correct
11 Correct 2682 ms 265968 KB Output is correct
12 Correct 2805 ms 267124 KB Output is correct
13 Correct 2836 ms 263424 KB Output is correct
14 Correct 1273 ms 255168 KB Output is correct
15 Correct 1255 ms 256620 KB Output is correct
16 Correct 4 ms 760 KB Output is correct
17 Correct 5 ms 888 KB Output is correct
18 Correct 5 ms 888 KB Output is correct
19 Correct 1 ms 888 KB Output is correct
20 Correct 2666 ms 240628 KB Output is correct
21 Correct 2887 ms 259676 KB Output is correct
22 Correct 2655 ms 262532 KB Output is correct
23 Correct 1357 ms 249228 KB Output is correct
24 Correct 140 ms 14860 KB Output is correct
25 Correct 151 ms 16508 KB Output is correct
26 Correct 155 ms 16364 KB Output is correct
27 Correct 1208 ms 247604 KB Output is correct
28 Correct 1210 ms 249392 KB Output is correct
29 Correct 4 ms 888 KB Output is correct
30 Correct 7 ms 888 KB Output is correct
31 Correct 4 ms 888 KB Output is correct
32 Correct 3 ms 888 KB Output is correct
33 Correct 1867 ms 269288 KB Output is correct
34 Correct 2130 ms 265752 KB Output is correct
35 Correct 2451 ms 260768 KB Output is correct
36 Correct 2948 ms 245192 KB Output is correct
37 Correct 353 ms 22912 KB Output is correct
38 Correct 270 ms 23672 KB Output is correct
39 Correct 348 ms 22840 KB Output is correct
40 Correct 272 ms 23672 KB Output is correct
41 Correct 348 ms 22772 KB Output is correct
42 Correct 278 ms 23672 KB Output is correct
43 Correct 1230 ms 247752 KB Output is correct
44 Correct 1224 ms 249216 KB Output is correct
45 Correct 124 ms 13624 KB Output is correct
46 Correct 174 ms 14064 KB Output is correct
47 Correct 1161 ms 88216 KB Output is correct
48 Correct 2595 ms 263016 KB Output is correct
49 Correct 170 ms 17896 KB Output is correct
50 Correct 162 ms 17980 KB Output is correct
51 Correct 174 ms 18088 KB Output is correct
52 Correct 185 ms 18664 KB Output is correct
53 Correct 170 ms 18664 KB Output is correct
54 Correct 194 ms 18664 KB Output is correct