oj.uz

Submission #167614

# Submission time Handle Problem Language Result Execution time Memory
167614 2019-12-09T06:07:06 Z qkxwsm Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 207412 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

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 y1 orz
#define y2 tmw
#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
#define INF 1000000007

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;
bitset<MAXN> state;
pii quer[MAXN];
unordered_map<int, ll> fen[MAXN];
int lst[MAXN];
set<int> lts, rts;
int ans;

void upd(int x, int y, int val)
{
	for (int e = x + 1; e <= N; e += e & (-e))
	{
		for (int f = y + 1; f <= N; f += f & (-f))
		{
			fen[e][f] += val;
		}
	}
}
ll qry(int x, int y)
{
	ll res = 0;
	for (int e = x + 1; e; e -= e & (-e))
	{
		for (int f = y + 1; f; f -= f & (-f))
		{
			auto it = fen[e].find(f);
			if (it != fen[e].end())
			{
				res += it -> se;
			}
		}
	}
	return res;
}
void del(int idx, int t)
{
	int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
	lts.erase(lt); rts.erase(rt);
	upd(lt, N - 1 - rt, t - lst[lt]);
	if (lt != idx)
	{
		lst[lt] = t;
		lts.insert(lt);
		rts.insert(idx - 1);
	}
	if (rt != idx)
	{
		lst[idx + 1] = t;
		lts.insert(idx + 1);
		rts.insert(rt);
	}
}
void ins(int idx, int t)
{
	if (rts.find(idx - 1) != rts.end() && lts.find(idx + 1) != lts.end())
	{
		int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
		rts.erase(idx - 1);
		lts.erase(idx + 1);
		upd(lt, N - idx, t - lst[lt]);
		upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
		lst[lt] = t;
	}
	else if (rts.find(idx - 1) != rts.end())
	{
		int lt = *prev(lts.UB(idx));
		rts.erase(idx - 1);
		rts.insert(idx);
		upd(lt, N - idx, t - lst[lt]);
		lst[lt] = t;
	}
	else if (lts.find(idx + 1) != lts.end())
	{
		int rt = *rts.LB(idx);
		lts.erase(idx + 1);
		lts.insert(idx);
		upd(idx + 1, N - 1 - rt, t - lst[idx + 1]);
		lst[idx] = t;
	}
	else
	{
		lts.insert(idx);
		rts.insert(idx);
		lst[idx] = t;
	}
}

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');
	}
	FOR(i, 0, N)
	{
		if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
		if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
	}
	for (auto it = lts.begin(); it != lts.end(); it++)
	{
		lst[*it] = -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};
		}
	}
	lts.clear(); rts.clear();
	FOR(i, 0, N)
	{
		if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
		if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
	}
	FOR(i, 0, Q)
	{
		if (quer[i].fi == -1)
		{
			int idx = quer[i].se;
			if (!state[idx])
			{
				ins(idx, i);
			}
			else
			{
				del(idx, i);
			}
			state[idx] = state[idx] ^ 1;
		}
		else
		{
			int lt = quer[i].fi, rt = quer[i].se;
			ans = qry(lt, N - 1 - rt);
			auto it = rts.LB(rt);
			if (it != rts.end())
			{
				auto jt = prev(lts.UB(*it));
				if (*jt <= lt)
				{
					int t = lst[*jt];
					ans += (i - t);
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19576 KB Output is correct
2 Correct 20 ms 19576 KB Output is correct
3 Correct 20 ms 19576 KB Output is correct
4 Correct 21 ms 19540 KB Output is correct
5 Correct 20 ms 19576 KB Output is correct
6 Correct 20 ms 19576 KB Output is correct
7 Correct 20 ms 19576 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 23056 KB Output is correct
2 Correct 376 ms 23252 KB Output is correct
3 Correct 1004 ms 27128 KB Output is correct
4 Correct 4807 ms 156728 KB Output is correct
5 Execution timed out 5085 ms 170504 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19960 KB Output is correct
2 Correct 25 ms 19912 KB Output is correct
3 Correct 31 ms 19960 KB Output is correct
4 Correct 24 ms 19576 KB Output is correct
5 Execution timed out 5024 ms 207412 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19704 KB Output is correct
2 Correct 22 ms 19832 KB Output is correct
3 Correct 23 ms 19920 KB Output is correct
4 Correct 23 ms 19984 KB Output is correct
5 Correct 1914 ms 38428 KB Output is correct
6 Correct 4292 ms 129088 KB Output is correct
7 Execution timed out 5049 ms 166628 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19576 KB Output is correct
2 Correct 20 ms 19576 KB Output is correct
3 Correct 20 ms 19576 KB Output is correct
4 Correct 21 ms 19540 KB Output is correct
5 Correct 20 ms 19576 KB Output is correct
6 Correct 20 ms 19576 KB Output is correct
7 Correct 20 ms 19576 KB Output is correct
8 Correct 276 ms 23056 KB Output is correct
9 Correct 376 ms 23252 KB Output is correct
10 Correct 1004 ms 27128 KB Output is correct
11 Correct 4807 ms 156728 KB Output is correct
12 Execution timed out 5085 ms 170504 KB Time limit exceeded
13 Halted 0 ms 0 KB -