Submission #399556

#	Time	Username	Problem	Language	Result	Execution time	Memory
399556		saarang123	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5061 ms	2268 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
const int mxn = 103;
int cnt[mxn][mxn], a[mxn], bit[mxn];
int n, q;

void upd(int x, int v) {
	a[x] ^= 1;
	for(; x <= n; x += (x & -x))
		bit[x] += v;
}

int qry(int x) {
	int res = 0;
	for(; x > 0; x -= (x & -x))
		res += bit[x];
	return res;	
}

int qry(int l, int r) { return qry(r) - qry(l - 1); }

void setup() {
	for(int i = 1; i <= n; i++)
    	for(int j = i; j <= n; j++)
    		if(qry(i, j) == j - i + 1)
    			cnt[i][j]++;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
    	char c; cin >> c;
    	if(c - '0')
    		upd(i, 1);
    }
    setup();
    while(q--) {
    	string s; cin >> s;
    	if(s == "toggle") {
    		int x, v;
    		cin >> x;
    		v = a[x] ? -1 : 1;
    		upd(x, v);
    	} else {
    		int l, r;
    		cin >> l >> r;
    		cout << cnt[l][r - 1] << '\n';
    	}
    	setup();
    }
    return 0;
}

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