oj.uz

답안 #383226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383226 2021-03-29T08:52:34 Z milleniumEeee 가로등 (APIO19_street_lamps) C++17
20 / 100
 908 ms 43016 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 <int> pref[MAXN];

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]);
		}
	}
	
	//cout << "seg: " << endl;
	//for (int i = 1; i <= n; i++) {
		//cout << i << ": " << endl;
		//for (auto el : seg[i]) {
			//cout << el.fr << " " << el.sc << endl;
		//}
	//}
	
	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].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;
			}
		}
	}
}

/*
6 4
101001
toggle 2 
toggle 2
toggle 4
query 2 3
*/

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 29036 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 18016 KB Output is correct
2 Correct 443 ms 18316 KB Output is correct
3 Correct 434 ms 18572 KB Output is correct
4 Correct 572 ms 34908 KB Output is correct
5 Correct 628 ms 41264 KB Output is correct
6 Correct 491 ms 35040 KB Output is correct
7 Correct 787 ms 24132 KB Output is correct
8 Correct 908 ms 43016 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 29036 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 29164 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 29036 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -