oj.uz

Submission #167548

# Submission time Handle Problem Language Result Execution time Memory
167548 2019-12-08T23:00:38 Z qkxwsm Street Lamps (APIO19_street_lamps) C++14
20 / 100
 308 ms 16524 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 351313

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
int stor[MAXN];
int lst[MAXN];
pii quer[MAXN];
bitset<MAXN> state;

int seg[3 * MAXN];
void update(int w, int L, int R, int a, int t)
{
	if (L == R)
	{
		seg[w] = t;
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid)
	{
		update(w << 1, L, mid, a, t);
	}
	else
	{
		update(w << 1 | 1, mid + 1, R, a, t);
	}
	seg[w] = max(seg[w << 1], seg[w << 1 | 1]);
}
int query(int w, int L, int R, int a, int b)
{
	if (a <= L && R <= b)
	{
		return seg[w];
	}
	int mid = (L + R) >> 1, res = -69;
	if (a <= mid)
	{
		ckmax(res, query(w << 1, L, mid, a, b));
	}
	if (mid < b)
	{
		ckmax(res, query(w << 1 | 1, mid + 1, R, a, b));
	}
	return res;
}


int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(12);
	cerr << fixed << setprecision(4);
	cin >> N >> Q;
	string temps; cin >> temps;
	FOR(i, 0, N)
	{
		state[i] = (temps[i] == '1');
		lst[i] = -1;
		if (state[i])
		{
			update(1, 0, N - 1, i, -1);
		}
		else
		{
			update(1, 0, N - 1, i, Q + 1);
		}
	}
	FOR(i, 0, Q)
	{
		cin >> temps;
		int x, y;
		if (temps[0] == 't')
		{
			cin >> x; x--;
			quer[i] = {-1, x};
		}
		else
		{
			cin >> x >> y; x--; y -= 2;
			quer[i] = {x, y};
		}
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			update(1, 0, N - 1, idx, i);
		}
		else
		{
			int lt = quer[i].fi, rt = quer[i].se;
			int mn = query(1, 0, N - 1, lt, rt);
			if (mn > i)
			{
				cout << "0\n";
			}
			else
			{
				cout << i - mn << '\n';
			}
		}
	}
	//for each guy, store: when was i turned on?
	return 0;
}

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 6268 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 380 KB Output is correct
5 Correct 179 ms 12760 KB Output is correct
6 Correct 225 ms 13408 KB Output is correct
7 Correct 257 ms 14280 KB Output is correct
8 Correct 305 ms 16400 KB Output is correct
9 Correct 92 ms 6008 KB Output is correct
10 Correct 102 ms 6460 KB Output is correct
11 Correct 102 ms 6648 KB Output is correct
12 Correct 305 ms 15064 KB Output is correct
13 Correct 308 ms 16524 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 -