Submission #498425

#	Time	Username	Problem	Language	Result	Execution time	Memory
498425		Karliver	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	81 ms	20876 KiB

street_lamps

	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int mxn = 3e5+2;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
template<class T> struct SegTree { // cmb(ID,b) = b
	const T ID{0}; T cmb(T a, T b) { return max(a,b); } 
	int n; V<T> seg;
	void init(int _n) { // upd, query also work if n = _n
		for (n = 1; n < _n; ) n *= 2; 
		seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = cmb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// associative op on [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = cmb(ra,seg[l++]);
			if (r&1) rb = cmb(seg[--r],rb);
		}
		return cmb(ra,rb);
	}
	
};

SegTree<int> S;
int P[102][102];
int lst[mxn], cnt[mxn];
void solve() {

	int n, q;
	cin >> n >> q;

	string s;
	cin >> s;
	bool second_case = 1;
	V<pair<string, pair<int, int>>> E;
	forn(i, q) {
		string type;
		cin >> type;
		if(type == "toggle") {
			int x;
			cin >> x;
			E.push_back({type, {x, 0}});
		}
		else {
			int l, r;
			cin >> l >> r;
			second_case &= (r-l == 1);
			E.push_back({type, {l, r-1}});
		}
	}

	if(n <= 100 && q <= 100) {
		forn(i, n) P[0][i] = (i == 0 ? 0 : P[0][i-1]) + (s[i] == '1' ? 1 : 0);
		int Q = 1;
		for(auto &[tt, gs] : E) {
			auto [l, r] = gs;
			if(tt == "toggle") {
				--l;
				s[l] = (s[l] == '1' ? '0' : '1');
			}
			else {
				--l;
				int ret = 0;
				forn(pt, Q) {
					int tot = P[pt][r-1];
					if(l)tot -= P[pt][l-1];
					if(tot == r-l)
						++ret;
				}
				cout << ret << '\n';
			}
			forn(i, n) P[Q][i] = (i == 0 ? 0 : P[Q][i-1]) + (s[i] == '1' ? 1 : 0);
			Q++;
		}
		return;

	}

	if(second_case) {
		forn(i, n) {
			if(s[i] == '1')
				lst[i] = 0;
			else
				lst[i] = INF;
		}
		int Q = 1; 
		for(auto &[tt, gs] : E) {
			auto [l, r] = gs;

			if(tt == "toggle") {
				--l;
				if(s[l] == '1') {
					cnt[l] += Q-lst[l]-1;
				}
				else {
					lst[l] = Q;
				}
				s[l] = (s[l] == '1' ? '0' : '1');
			}
			else {
				assert(l==r);
				--l;
				cout << cnt[l] + (s[l] == '1' ? Q-lst[l] : 0) << '\n';
			}
			++Q;
		}
		return;
	}

	
	assert(false);


	



}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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