oj.uz

Submission #399556

# Submission time Handle Problem Language Result Execution time Memory
399556 2021-05-06T05:30:58 Z saarang123 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 2268 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 324 KB Output is correct
6 Correct 5 ms 204 KB Output is correct
7 Correct 5 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 2268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 324 KB Output is correct
6 Correct 5 ms 204 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Execution timed out 5061 ms 2268 KB Time limit exceeded
9 Halted 0 ms 0 KB -