oj.uz

Submission #721783

# Submission time Handle Problem Language Result Execution time Memory
721783 2023-04-11T07:15:27 Z LittleCube Street Lamps (APIO19_street_lamps) C++17
20 / 100
 3105 ms 524288 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, Q, ans[300005], state[300005];
map<pii, int> mp;
vector<pair<pii, int>> in[300005], out[300005];
vector<pii> qu[300005];

void insert(int p, int t)
{
	auto rter = mp.upper_bound(pii(p, 0));
	auto lter = prev(rter);
	int l = p, r = p;
	if(rter != mp.end() && rter->F.F == p + 1)
	{
		auto [a, b] = rter->F;
	   	int s = rter->S;
		in[a].emplace_back(make_pair(pii(s, t), a));
		out[b].emplace_back(make_pair(pii(s, t), a));
		r = b;
		mp.erase(rter);
	}
	if(lter->F.S == p - 1)
	{
		auto [a, b] = lter->F; 
	   	int s = lter->S;
		in[a].emplace_back(make_pair(pii(s, t), a));
		out[b].emplace_back(make_pair(pii(s, t), a));
		l = a;
		mp.erase(lter);
	}
	mp[pii(l, r)] = t + 1;
}

void erase(int p, int t)
{
	auto iter = prev(mp.lower_bound(pii(p, N + 1)));
	auto [a, b] = iter->F;
    int s = iter->S;
	in[a].emplace_back(make_pair(pii(s, t), a));
	out[b].emplace_back(make_pair(pii(s, t), a));
	mp.erase(iter);
	if(a < p)
		mp[pii(a, p - 1)] = t + 1;
	if(p < b)
		mp[pii(p + 1, b)] = t + 1;
}

struct segTree
{
	vector<int> seg, l, r, lazy;
	inline int newnode()
	{
		seg.emplace_back(0);
		l.emplace_back(0);
		r.emplace_back(0);
		lazy.emplace_back(0);
		return (int)seg.size() - 1;
	}
	inline void apply(int val, int i, int L, int R)
	{
		lazy[i] += val;
		seg[i] += val * (R - L + 1);
	}	
	void modify(int mL, int mR, int val, int i = 0, int L = 1, int R = Q)
	{
		if(mL <= L && R <= mR)
			apply(val, i, L, R);
		else if(R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			if(!l[i]) l[i] = newnode();
			if(!r[i]) r[i] = newnode();
			apply(lazy[i], l[i], L, mid);
			apply(lazy[i], r[i], mid + 1, R);
			lazy[i] = 0;
			modify(mL, mR, val, l[i], L, mid);
			modify(mL, mR, val, r[i], mid + 1, R);
			seg[i] = seg[l[i]] + seg[r[i]];
		}
	}
	int query(int mL, int mR, int i = 0, int L = 1, int R = Q)
	{
		if(mL <= L && R <= mR)
			return seg[i];
		else if(R < mL || mR < L)
			return 0;
		else
		{
			int mid = (L + R) / 2;
			if(!l[i]) l[i] = newnode();
			if(!r[i]) r[i] = newnode();
			apply(lazy[i], l[i], L, mid);
			apply(lazy[i], r[i], mid + 1, R);
			lazy[i] = 0;
			return query(mL, mR, l[i], L, mid) + query(mL, mR, r[i], mid + 1, R);
		}
	}

} tree[300005];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	mp[pii(-2, -2)] = -1;
	cin >> N >> Q;
	for(int i = 1; i <= N; i++)
	{
		char c;
		cin >> c;
		state[i] = c - '0';
	}
	for (int i = 1; i <= N; i++)
		if(state[i])
		{
			int j = i;
			while(state[j + 1])
				j++;
			mp[pii(i, j)] = 1;
			i = j;
		}	
	for (int i = 1; i <= Q; i++)
	{
		string s;
		int a, b;
		cin >> s;
		if(s == "toggle")
		{
			ans[i] = -1;
			cin >> a;
			state[a] ^= 1;
			if(state[a])
				insert(a, i);
			else 
				erase(a, i);
		}
		else if(s == "query")
		{
			cin >> a >> b;
			b--;
			qu[b].emplace_back(pii(a, i));
		}
		//for (auto [p, v] : mp)
		//	cerr << "(" << p.F << ", " << p.S << ") " << v << "  ";
		//cerr << '\n';
	}
	mp.erase(mp.begin());
	for (auto [p, v] : mp)
	{
		auto [a, b] = p;
		in[a].emplace_back(make_pair(pii(v, Q), a));
		out[b].emplace_back(make_pair(pii(v, Q), a));
	}

	for (int i = 1; i <= N; i++)
		tree[i].newnode();

	for (int i = 1; i <= N; i++)
	{
		for (auto [p, k] : in[i])
		{
			auto [l, r] = p;
			//cerr << l << ' ' << r << ' ' << k << ' ' << i << '\n';
			for (; k <= N; k += (k & -k))
				tree[k].modify(l, r, 1);
		}
		
		for (auto [r, j] : qu[i])
		{
			for (; r > 0; r -= (r & -r))
				ans[j] += tree[r].query(1, j);
		}

		for (auto [p, k] : out[i])
		{
			auto [l, r] = p;
			//cerr << l << ' ' << r << ' ' << k << ' ' << i <<  " out " << '\n';
			for (; k <= N; k += (k & -k))
				tree[k].modify(l, r, -1);

		}


	}
	for (int i = 1; i <= Q; i++)
		if(ans[i] >= 0)
			cout << ans[i] << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 33 ms 49600 KB Output is correct
3 Correct 31 ms 49640 KB Output is correct
4 Correct 31 ms 49636 KB Output is correct
5 Correct 33 ms 49644 KB Output is correct
6 Correct 32 ms 49680 KB Output is correct
7 Correct 34 ms 49620 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1346 ms 205644 KB Output is correct
2 Correct 1865 ms 260776 KB Output is correct
3 Runtime error 2746 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 51020 KB Output is correct
2 Correct 37 ms 51068 KB Output is correct
3 Correct 44 ms 50924 KB Output is correct
4 Correct 41 ms 50828 KB Output is correct
5 Runtime error 3105 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 50792 KB Output is correct
2 Correct 46 ms 50932 KB Output is correct
3 Correct 46 ms 51048 KB Output is correct
4 Correct 44 ms 51032 KB Output is correct
5 Runtime error 1947 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 33 ms 49600 KB Output is correct
3 Correct 31 ms 49640 KB Output is correct
4 Correct 31 ms 49636 KB Output is correct
5 Correct 33 ms 49644 KB Output is correct
6 Correct 32 ms 49680 KB Output is correct
7 Correct 34 ms 49620 KB Output is correct
8 Correct 1346 ms 205644 KB Output is correct
9 Correct 1865 ms 260776 KB Output is correct
10 Runtime error 2746 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -