Submission #392603

#	Time	Username	Problem	Language	Result	Execution time	Memory
392603		BorisBarca	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	310 ms	19680 KiB

street_lamps

/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <string> vs;

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

const int N = 3e5 + 10;
int n, q, on[N];

struct query{
	int t;
	int l, r;
} Q[N];

namespace prvi{
	int ans[N];
	void solve(){
		REP(j, q){
			if (Q[j].t == 2){
				bool ok = 1;
				FOR(k, Q[j].l, Q[j].r){
					if (!on[k])
						ok = 0;
				}
				if (ok)
					ans[j]++;
			}
		}
		REP(i, q){
			if (Q[i].t == 1){
				on[Q[i].l] = 1 - on[Q[i].l];
			} else
				cout << ans[i] << '\n';
			REP(j, q){
				if (Q[j].t == 2){
					bool ok = 1;
					FOR(k, Q[j].l, Q[j].r){
						if (!on[k])
							ok = 0;
					}
					if (ok)
						ans[j]++;
				}
			}
		}
	}
}

namespace drugi{
	int ans[N], lst[N];
	void solve(){
		REP(i, q){
			if (Q[i].t == 1){
				int x = Q[i].l;
				if (on[x]){
					ans[x] += i - lst[x] + 1;
					on[x] = 0;
				} else {
					lst[x] = i + 1;
					on[x] = 1;
				}
			} else {
				cout << ans[Q[i].l] + (on[Q[i].l] * (i - lst[Q[i].l] + 1)) << '\n';
			}
		}
	}
}

const int LOG = 19;
const int OFF = 1 << LOG;

namespace treci{
	struct tournament{
		int t[2 * OFF], maxi[2 * OFF], off;

		void init(int n){
			for (off = 1; off < n; off *= 2);
			memset(t, 0, sizeof t);
		}

		void upd(int x, int y){
			t[x + off]++;
			maxi[x + off] = y;
			for (int i = (x + off) / 2; i; i /= 2)
				t[i] = t[i * 2] + t[i * 2 + 1], maxi[i] = max(maxi[i * 2], maxi[i * 2 + 1]);
		}

		pii query(int node, int a, int b, int lo, int hi){
			if (a > hi || b < lo)
				return {0, 0};
			if (a >= lo && b <= hi)
				return {t[node], maxi[node]};
			int mid = (a + b) / 2;
			pii l = query(node * 2, a, mid, lo, hi);
			pii r = query(node * 2 + 1, mid + 1, b, lo, hi);
			return {l.X + r.X, max(l.Y, r.Y)};
		}
	} T;
	
	void solve(){
		T.init(n);
		REP(i, n)
			if (on[i])
				T.upd(i, 0);
		REP(i, q){
			if (Q[i].t == 1){
				T.upd(Q[i].l, i + 1);
			} else {
				pii ans = T.query(1, 0, T.off - 1, Q[i].l, Q[i].r - 1);
				if (ans.X == Q[i].r - Q[i].l)
					cout << i + 1 - ans.Y << '\n';
				else
					cout << 0 << '\n';
			}
		}
	}


}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q;
	REP(i, n){
		char c; cin >> c;
		on[i] = c - '0';
	}
	
	bool dva = 1;
	REP(i, q){
		string s; cin >> s;
		if (s[0] == 't'){
			int x; cin >> x;
			x--;
			Q[i].t = 1, Q[i].l = x;
		} else {
			int l, r; cin >> l >> r;
			Q[i].t = 2;
			l--, r--;
			if (r - l > 1)
				dva = 0;
			Q[i].l = l, Q[i].r = r;
		}
	}

	if (max(n, q) <= 105){
		prvi::solve();
	} else if (dva){
		drugi::solve();
	} else
		treci::solve();	

	return 0;
}

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