Submission #595488

#	Time	Username	Problem	Language	Result	Execution time	Memory
595488		penguinhacker	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	2040 ms	77848 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=3e5;
int n, q, ans[mxN], st[mxN];
string s;
vector<int> changes[mxN];
vector<ar<int, 2>> ls[mxN];
vector<ar<int, 4>> queries;

struct ft {
	ll ft[mxN+1];
	void upd(int i, ll x) {
		for (++i; i<=mxN; i+=i&-i)
			ft[i]+=x;
	}
	ll qry(int i) {
		ll r=0;
		for (++i; i; i-=i&-i)
			r+=ft[i];
		return r;
	}
} ft1, ft2;

void upd(int l, int r, int x) {
	ft1.upd(l, -(ll)(l-1)*x);
	ft2.upd(l, x);
	ft1.upd(r+1, (ll)r*x);
	ft2.upd(r+1, -x);
}

ll qry(int i) {
	return i*ft2.qry(i)+ft1.qry(i);
}

void solve(int l, int r) {
	if (l==r)
		return;
	int mid=(l+r)/2;
	solve(l, mid);
	solve(mid+1, r);
	vector<ar<int, 4>> tmp;
	vector<ar<int, 3>> rb;
	tmp.reserve(r-l+1);
	for (int i=l, j=mid+1; tmp.size()<r-l+1;) {
		if (j>r||i<=mid&&queries[i][0]<=queries[j][0]) {
			if (queries[i][2]!=-1) { // update
				upd(queries[i][1], queries[i][2], queries[i][3]);
				rb.push_back({queries[i][1], queries[i][2], -queries[i][3]});
			}
			tmp.push_back(queries[i++]);
		} else {
			if (queries[j][2]==-1) // query
				ans[queries[j][1]]+=qry(queries[j][1]);
			tmp.push_back(queries[j++]);
		}
	}
	for (int i=l; i<=r; ++i)
		queries[i]=tmp[i-l];
	for (auto [l, r, x] : rb)
		upd(l, r, x);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> s;
	for (int i=0; i<n; ++i)
		if (s[i]=='0')
			changes[i].push_back(-1);
	for (int i=0; i<q; ++i) {
		string type;
		cin >> type;
		if (type=="toggle") {
			int x;
			cin >> x, --x;
			changes[x].push_back(i);
			ans[i]=-1;
		} else {
			int l, r;
			cin >> l >> r, --l, r-=2;
			ls[r].push_back({l, i});
		}
	}
	set<ar<int, 3>> s;
	s.insert({0, q-1, 0});
	queries.push_back({0, 0, q-1, 1});
	for (int i=0; i<n; ++i) {
		for (int j=0; j<changes[i].size(); j+=2) {
			int b=j+1<changes[i].size()?changes[i][j+1]:q-1;
			ar<int, 3> seg={changes[i][j]+1, b, i+1};
			auto it=s.lower_bound({seg[0]});
			for (; it!=s.end()&&seg[1]>=(*it)[0];) {
				if ((*it)[1]<=seg[1]) { // erase entire segment
					queries.push_back({(*it)[2], (*it)[0], (*it)[1], -1});
					it=s.erase(it);
				} else { // erase part of this segment
					int rb=(*it)[1], val=(*it)[2];
					queries.push_back({val, (*it)[0], seg[1], -1});
					s.erase(it);
					it=s.insert({seg[1]+1, rb, val}).first;
				}
			}
			if (it!=s.begin()) {
				--it;
				if ((*it)[1]>=seg[0]) {
					int lb=(*it)[0], val=(*it)[2];
					queries.push_back({(*it)[2], seg[0], (*it)[1], -1});
					s.erase(it);
					s.insert({lb, seg[0]-1, val});
				}
			}
			queries.push_back({seg[2], seg[0], seg[1], 1});
			s.insert(seg);
		}
		for (auto [l, t] : ls[i])
			queries.push_back({l, t, -1});
	}
	//for (auto x : queries)
	//	cout << x[0] << " " << x[1] << " " << x[2] << " " << x[3] << endl;
	solve(0, queries.size()-1);
	for (int i=0; i<q; ++i)
		if (~ans[i])
			cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:48:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |  for (int i=l, j=mid+1; tmp.size()<r-l+1;) {
      |                         ~~~~~~~~~~^~~~~~
street_lamps.cpp:49:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |   if (j>r||i<=mid&&queries[i][0]<=queries[j][0]) {
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int j=0; j<changes[i].size(); j+=2) {
      |                 ~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:93:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    int b=j+1<changes[i].size()?changes[i][j+1]:q-1;
      |          ~~~^~~~~~~~~~~~~~~~~~

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