oj.uz

Submission #163962

# Submission time Handle Problem Language Result Execution time Memory
163962 2019-11-16T12:18:27 Z sams Street Lamps (APIO19_street_lamps) C++14
20 / 100
 334 ms 12176 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

struct ND
{
	int s, m;	
} seg[4*maxn];

int n, q;
int v[maxn];
string ss;

ND op(ND a, ND b)
{
	return {a.s + b.s, max(a.m, b.m)};
}

void build(int u = 1, int l = 1, int r = n)
{
	if(l == r)
	{
		seg[u] = {v[l], 0};
		return;
	}

	int mid = (l+r) >> 1;

	build(2*u, l, mid);
	build(2*u + 1, mid + 1, r);

	seg[u] = op(seg[2*u], seg[2*u+1]);
}

ND query(int a, int b, int u = 1, int l = 1 , int r = n)
{
	if(r < a || l > b) return {0, 0};
	if(a <= l && r <= b) return seg[u];

	int mid = (l + r) >> 1;

	return op(query(a, b, 2*u, l, mid), query(a, b, 2*u+1, mid +1, r));
}

void upd(int a, int t, int u = 1, int l = 1, int r = n)
{
	if(l == r)
	{
		v[l] = (v[l] == 1)? 0 : 1;

		seg[u] = {v[l], t};

		return;
	}

	int mid = (l + r) >> 1;

	if(a <= mid) upd(a, t, 2*u, l, mid);
	else upd(a, t, 2*u +1, mid +1, r);

	seg[u] = op(seg[2*u], seg[2*u +1]);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> q >> ss;

	for(int i = 0 ; i < n ; ++i)
	{
		if(ss[i] == '0') v[i + 1] = 0;
		else v[i + 1] = 1;
	}

	build();

	for(int i = 1 ; i <= q ; ++i)
	{
		string S;
		int l, r;
		cin >> S >> l;

		if(S == "query")
		{
			cin >> r;

			ND qr = query(l, r-1);

			if(qr.s == r - l) cout << i - qr.m << "\n";
			else cout << "0\n";
		}
		else
		{
			upd(l, i);
		}
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 173 ms 10124 KB Output is correct
6 Correct 261 ms 10476 KB Output is correct
7 Correct 255 ms 10504 KB Output is correct
8 Correct 334 ms 12176 KB Output is correct
9 Correct 103 ms 1240 KB Output is correct
10 Correct 112 ms 1272 KB Output is correct
11 Correct 116 ms 1400 KB Output is correct
12 Correct 298 ms 10748 KB Output is correct
13 Correct 327 ms 12172 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -