제출 #498447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498447		Karliver	가로등 (APIO19_street_lamps)	C++17	40 / 100	123 ms	28632 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);
	}
	
};
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
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) {
		
		int Q = 1;
		V<PR<int>> D[mxn];
		for(auto &[tt, gs] : E) {
			auto [l, r] = gs;

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

	S.init(n);
	forn(i, n) {
		if(s[i] == '1') {
			S.upd(i, 0);
		}
		else {
			S.upd(i, INF);
		}
	}
	int Q = 1;
	for(auto &[tt, gs] : E) {
		auto [l, r] = gs;
		--l;
		if(tt == "toggle") {
			assert(s[l] == '1');
			S.upd(l, Q);
		}
		else {
			int ret = S.query(l, r-1);
			if(ret == INF)
				ret = 0;
			else
				ret = Q-ret;
			cout << ret << '\n';
		}
		++Q;
	}


}
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: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20