oj.uz

Submission #207898

# Submission time Handle Problem Language Result Execution time Memory
207898 2020-03-09T11:38:35 Z Segtree Street Lamps (APIO19_street_lamps) C++14
20 / 100
 4643 ms 49804 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")

#define N 300010
namespace seg{
	ll dat[2*N];
	void init(){
		rep(i,2*N)dat[i]=0;
	}
	void add(ll i,ll x){
		if(i<0)return;
		i+=N;
		for(;i;i>>=1)dat[i]+=x;
	}
	ll sum(ll l,ll r){
		l+=N,r+=N+1;
		ll res=0;
		for(ll a=l,b=r;a<b;a>>=1,b>>=1){
			if(a&1)res+=dat[a++];
			if(b&1)res+=dat[--b];
		}
		return res;
	}
}
typedef struct range{
	ll l,r,val;
	bool operator<(const range&key)const{
		return this->l<key.l;
	}
}range;
namespace DS{
	set<range> S;
	void init(){
		seg::init();
		S.clear();
	}
	set<range>::iterator erase(set<range>::iterator it){
		if(it==S.end())return it;
		seg::add(it->val,-(it->r-it->l+1));
		return S.erase(it);
	}
	void ins(ll l,ll r,ll val){
		if(l>r)return;
		seg::add(val,r-l+1);
		S.insert((range){l,r,val});
	}
	void insert(ll l,ll r,ll val){
		//cerr<<"beg_sum:"<<seg::sum(0,N-1)<<endl;
		range x=(range){l,r,val};
		{//[l,r]に完全に含まれているものを消す
			auto it=S.lower_bound(x);
			while(1){
				if(it==S.end())break;
				if(r<it->r)break;
				it=erase(it);
			}
		}
		bool done=0;
		{//[l,r]を完全に含んでいるものがある場合
			auto it=S.upper_bound(x);
			if(it!=S.begin()){
				it--;
				if(it->l<=l&&r<=it->r){
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(itl,l-1,itval);
					ins(r+1,itr,itval);
					done=1;
					ll sum=0;
					for(auto e:S)sum+=e.r-e.l+1;
				}
			}
		}
		if(done==0){//そうでない場合
			{//右側で交差しているもの
				auto it=S.upper_bound(x);
				if(it!=S.end()){
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(r+1,itr,itval);
				}
			}
			{//左側で交差しているもの
				auto it=S.lower_bound(x);
				if(it!=S.begin()){
					it--;
					ll itl=it->l,itr=it->r,itval=it->val;
					erase(it);
					ins(itl,l-1,itval);
				}
			}
		}
		//cerr<<"add:"<<l<<" "<<r<<" "<<val<<endl;
		seg::add(val,r-l+1);
		S.insert((range){l,r,val});
		//cerr<<"seg_sum:"<<seg::sum(0,N-1)<<endl;
	}
};
ll n,q;
string s;
vector<ll> upd[N];
typedef struct query{
	ll a,b,id;
}query;
vector<query> qrys[N];
ll fans[N];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>q;
	//n=Data::n,q=Data::q;
	cin>>s;
	//s=Data::s;
	rep(i,n){
		if(s[i]=='0')upd[i].push_back(0);
	}
	bool fi=1;
	ll toggles=0;
	ll rui[N];
	for(int t=1;t<=q;t++){
		string typ;
		cin>>typ;
		//typ=Data::typ[t-1];
		if(typ=="toggle"){
			ll x;
			cin>>x;
			//x=Data::x[t-1];
			x--;
			if(s[x]=='0'){
				upd[x].push_back(t);
				s[x]='1';
			}
			else{
				upd[x].push_back(t);
				s[x]='0';
			}
			toggles=t;
		}
		if(typ=="query"){
			if(fi){
				rep(i,n)if(s[i]=='0')upd[i].push_back(t);
				rui[0]=0;
				for(int i=0;i<n;i++)rui[i+1]=rui[i]+(s[i]-'0');
				fi=0;
			}
			ll a,b;
			cin>>a>>b;
			//a=Data::a[t-1],b=Data::b[t-1];
			a--,b--;
			fans[t]=(rui[b]-rui[a]==b-a)*(t-1-toggles);
			qrys[b-1].push_back((query){a,b-1,t});
		}
	}
	DS::init();
	DS::ins(0,toggles,-1);
	for(int b=0;b<n;b++){
		for(int i=0;i+1<upd[b].size();i+=2){
			ll l=upd[b][i],r=upd[b][i+1]-1;
			DS::insert(l,r,b);
			//cerr<<"upd:"<<l<<" "<<r<<" "<<b<<endl;
		}
		for(query qry:qrys[b]){
			//cerr<<"qry:"<<qry.a<<" "<<qry.b<<" "<<qry.id<<endl;
			fans[qry.id]+=toggles+1-seg::sum(qry.a,qry.b);
		}
	}
	for(int i=toggles+1;i<=q;i++){
		cout<<fans[i]<<"\n";
		//FANS.push_back(fans[i]);
	}
}

Compilation message

street_lamps.cpp:14:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
street_lamps.cpp:15:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
street_lamps.cpp:16:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
street_lamps.cpp: In function 'void DS::insert(ll, ll, ll)':
street_lamps.cpp:92:9: warning: unused variable 'itl' [-Wunused-variable]
      ll itl=it->l,itr=it->r,itval=it->val;
         ^~~
street_lamps.cpp:101:19: warning: unused variable 'itr' [-Wunused-variable]
      ll itl=it->l,itr=it->r,itval=it->val;
                   ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:172:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<upd[b].size();i+=2){
               ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 19064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1121 ms 28280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 17 ms 19196 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 321 ms 39052 KB Output is correct
6 Correct 323 ms 36620 KB Output is correct
7 Correct 292 ms 33932 KB Output is correct
8 Correct 296 ms 30604 KB Output is correct
9 Correct 693 ms 26360 KB Output is correct
10 Correct 4643 ms 23012 KB Output is correct
11 Correct 705 ms 26360 KB Output is correct
12 Correct 4498 ms 22904 KB Output is correct
13 Correct 714 ms 29816 KB Output is correct
14 Correct 4628 ms 25464 KB Output is correct
15 Correct 367 ms 49804 KB Output is correct
16 Correct 307 ms 41868 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 19064 KB Output isn't correct
2 Halted 0 ms 0 KB -