oj.uz

Submission #383222

# Submission time Handle Problem Language Result Execution time Memory
383222 2021-03-29T08:44:23 Z milleniumEeee Street Lamps (APIO19_street_lamps) C++17
0 / 100
 92 ms 19040 KB 
#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int MAXN = (int)3e5 + 5;
const int INF = 1e9;

char c[MAXN];
vector <pii> seg[MAXN];
vector <pii> qvec;
vector <vector<int>> pref;

char rev(char x) {
	return (x == '1' ? '0' : '1');
}

signed main() {
	fastInp;
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		if (c[i] == '1') {
			seg[i].pb({0, INF});
		}
	}
	string type;
	for (int xod = 1, tiktak = 1; xod <= q; xod++, tiktak++) {
		cin >> type;
		if (type == "query") {
			int l, r;
			cin >> l >> r;
			assert(l + 1 == r);
			qvec.pb({xod, l});
		}
		if (type == "toggle") {
			int pos;
			cin >> pos;
			if (c[pos] == '0') {
				seg[pos].pb({xod, INF});
			}
			else if (c[pos] == '1') {
				seg[pos].back().second = xod - 1;
			}
			c[pos] = rev(c[pos]);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (seg[i].empty()) {
			continue;
		}
		for (int j = 0; j < szof(seg[i]); j++) {
			if (j == 0) {
				pref[i].pb(seg[i][j].sc - seg[i][j].fr + 1);
			} else {
				pref[i].pb(pref[i - 1].back() + seg[i][j].sc - seg[i][j].fr + 1);
			}
		}
	}
	
	for (auto el : qvec) {
		int tiktak = el.fr, pos = el.sc;
		if (seg[pos].empty()) {
			cout << 0 << endl;
		} else {
			if (seg[pos][0].fr < tiktak) {
				int l = 0, r = szof(seg[pos]);
				while (r - l > 1) {
					int mid = (l + r) >> 1;
					if (seg[pos][mid].fr < tiktak) {
						l = mid;
					} else {
						r = mid;
					}
				}
				int ans = 0;
				if (l >= 1) {
					ans = pref[pos][l - 1];
				}
				if (seg[pos][l].sc < tiktak) {
					ans += seg[pos][l].sc - seg[pos][l].fr + 1;
				} else {
					ans += (tiktak - 1) - seg[pos][l].fr + 1;
				}
				cout << ans << endl;
			} else {
				cout << 0 << endl;
			}
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 14828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 14828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 14828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 14828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -