oj.uz

Submission #163971

# Submission time Handle Problem Language Result Execution time Memory
163971 2019-11-16T12:49:28 Z sams Street Lamps (APIO19_street_lamps) C++14
40 / 100
 334 ms 13580 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], c[maxn], last[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(r - l == 1)
			{
				//cout << l << " " << i << " " << c[l] << " " << last[l] << "\n";
				(v[l])? cout << i - c[l] << "\n" : cout << last[l] - c[l] << "\n";
			}
			else
			{
				if(qr.s == r - l) cout << i - qr.m << "\n";
				else cout << "0\n";
			}
		}
		else
		{
			if(v[l] == 1)
			{
				last[l] = i;
			}
			else
			{
				c[l] += i - last[l];
				last[l] = i;
			}
			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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1268 KB Output is correct
2 Correct 120 ms 1332 KB Output is correct
3 Correct 143 ms 1528 KB Output is correct
4 Correct 261 ms 13196 KB Output is correct
5 Correct 255 ms 13580 KB Output is correct
6 Correct 246 ms 13224 KB Output is correct
7 Correct 261 ms 10764 KB Output is correct
8 Correct 268 ms 12144 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 213 ms 12556 KB Output is correct
6 Correct 233 ms 12684 KB Output is correct
7 Correct 281 ms 12944 KB Output is correct
8 Correct 334 ms 12216 KB Output is correct
9 Correct 103 ms 1272 KB Output is correct
10 Correct 110 ms 1276 KB Output is correct
11 Correct 115 ms 1400 KB Output is correct
12 Correct 327 ms 10804 KB Output is correct
13 Correct 324 ms 12172 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 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 -