Submission #402040

#	Time	Username	Problem	Language	Result	Execution time	Memory
402040		kai824	가로등 (APIO19_street_lamps)	C++17	0 / 100	203 ms	64364 KiB

street_lamps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;


typedef gp_hash_table<int, int, hash<int>> ht;
ht ft[300005];
int n=N;
#define ls(x) (x&(-x))
void update(int a,int b,int upd){
  //cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
  for(;a<=n;a+=ls(a)){
    for(int x=b;x<=n;x+=ls(x)){
      if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
      else ft[a][x]+=upd;
    }
  }
}
 
inline void upd(int l1, int l2, int r1, int r2, int v) {
	// add v to (l1, r1)
	/*for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] += v;*/
  update(l1,r1,v);
	
	// add -v to (l1, r2 + 1)
  update(l1,r2+1,-v);
	
	// add -v to (l2 + 1, r1)
	update(l2+1,r1,-v);
	
	// add v to (l2 + 1, r2 + 1)
	update(l2+1,r2+1,v);
}
 
inline int qry(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= ls(i))
		for (int j = y; j; j -= ls(j))
			r += ft[i][j];
	return r;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		A[i] = tmp - '0';
		if (A[i]) {
			if (i == 1 || !A[i - 1]) S.emplace(i, i);
			else {
				int lft = S.rbegin()->first;
				S.erase(--S.end());
				S.emplace(lft, i);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cin >> s;
		if (s == "toggle") {
			cin >> x;
			if (A[x]) {
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				assert(it != S.begin());
				--it;
				l = it->first;
				r = it->second + 1;
				
				// fix S
				S.erase(it);
				if (l < x) S.emplace(l, x - 1);
				if (x < r - 1) S.emplace(x + 1, r - 1);
				
				assert(l <= x && x + 1 <= r);
				// we know that [l, x] can currently reach [x + 1, r]
				upd(l, x, x + 1, r, i);
			} else {
				vector<set<pair<int, int> >::iterator> del;
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				if (it != S.end() && it->first == x + 1) r = it->second + 1, del.push_back(it);
				else r = x + 1;
				if (it != S.begin()) {
					--it;
					if (it->second == x - 1) l = it->first, del.push_back(it);
					else l = x;
				} else l = x;
				
				// fix S
				for (auto i : del) S.erase(i);
				S.emplace(l, r - 1);
				
				// we know that [l, x] cannot currently reach [x + 1, r]
				upd(l, x, x + 1, r, -i);
			}
			A[x] ^= 1;
		} else {
			cin >> a >> b;
			auto it = S.upper_bound(make_pair(a, (int)1e9));
			if (it != S.begin()) {
				--it;
				if (b <= it->second + 1) {
					cout << qry(a, b) + i << '\n';
					goto done;
				}
			}
			cout << qry(a, b) << '\n';
			done:;
		}
	}
}

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