Submission #1234501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234501		PlayVoltz	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	624 ms	51212 KiB

street_lamps

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct quad{
	int l, r, c;
	bool t;
};

int n;
vector<int> ans, ft;
vector<vector<quad> > quer;

void update(int i, int v){
	for (;i<=n;i+=i&-i)ft[i]+=v;
}

int calc(int i){
	int res=0;
	for (;i;i-=i&-i)res+=ft[i];
	return res;
}

int query(int l, int r){
	return calc(r)-calc(l-1);
}

bool custom(quad a, quad b){
	if (a.l==b.l)return a.t<b.t;
	return a.l<b.l;
}

void dnc(int l, int r){
	if (l>=r)return;
	int mid=(l+r)/2;
	vector<quad> vect;
	for (int i=l; i<=mid; ++i)for (auto c:quer[i])if (!c.t)vect.pb(c);
	for (int i=mid+1; i<=r; ++i)for (auto c:quer[i])if (c.t)vect.pb(c);
	sort(vect.begin(), vect.end(), custom);
	for (auto c:vect){
		if (c.t)ans[c.c]+=query(c.r, n);
		else update(c.r, c.c);
	}
	for (auto c:vect)if (!c.t)update(c.r, -c.c);
	dnc(l, mid);
	dnc(mid+1, r);
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int q, a, b;
	string ss;
	cin>>n>>q>>ss;
	ft.resize(n+1, 0);
	ans.resize(q+1, 0);
	vector<bool> t(n+1, 0);
	quer.resize(q+1);
	set<pair<pii, int> > s;
	for (int i=1, p=-1; i<=n; ++i){
		t[i]=ss[i-1]-'0';
		if (!t[i]&&p!=-1)s.insert(mp(mp(p, i-1), 0)), p=-1;
		if (t[i]&&p==-1)p=i;
		if (t[i]&&i==n)s.insert(mp(mp(p, i), 0));
	}
	for (int i=1; i<=q; ++i){
		cin>>ss;
		if (ss=="toggle"){
			cin>>a;
			ans[i]=-1;
			t[a]=!t[a];
			if (t[a]){
				int l=a, r=a;
				auto it=s.upper_bound(mp(mp(a, LLONG_MAX/2), LLONG_MAX/2));
				vector<pair<pii, int> > del;
				if (it!=s.end()&&it->fi.fi==a+1){
					r=it->fi.se;
					quer[i].pb({it->fi.fi, it->fi.se, i-it->se, 0});
					del.pb(*it);
				}
				if (it!=s.begin()&&(--it)->fi.se==a-1){
					l=it->fi.fi;
					quer[i].pb({it->fi.fi, it->fi.se, i-it->se, 0});
					del.pb(*it);
				}
				for (auto c:del)s.erase(c);
				s.insert(mp(mp(l, r), i));
			}
			else{
				pair<pii, int> temp=*(--s.upper_bound(mp(mp(a, LLONG_MAX/2), LLONG_MAX/2)));
				quer[i].pb({temp.fi.fi, temp.fi.se, i-temp.se, 0});
				s.erase(temp);
				if (temp.fi.fi<a)s.insert(mp(mp(temp.fi.fi, a-1), i));
				if (temp.fi.se>a)s.insert(mp(mp(a+1, temp.fi.se), i));
			}
		}
		else{
			cin>>a>>b, --b;
			auto it = s.upper_bound(mp(mp(b, LLONG_MAX/2), LLONG_MAX/2));
			if (it!=s.begin()&&(--it)->fi.fi<=a&&b<=it->fi.se)ans[i]=i-it->se;
			quer[i].pb({a, b, i, 1});
		}
	}
	dnc(1, q);
	for (int i=1; i<=q; ++i)if (ans[i]!=-1)cout<<ans[i]<<"\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20