Submission #255571

#	Time	Username	Problem	Language	Result	Execution time	Memory
255571		Berted	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	2368 ms	524292 KiB

street_lamps

#include <iostream>
#include <set>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;
using namespace __gnu_pbds;

struct chash {
    const int RANDOM = 6969420;
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
    int operator()(const pii& x) const { return (hash_f(x.fst) * 31 + hash_f(x.snd))^RANDOM; }
};


gp_hash_table<pii, int, chash> fwk; 
int n, q; 
string ar;
set<ppi> s;

inline void upd(int i, int j, int v)
{
	for (; i <= n; i += i & (-i))
	{
		for (int k = j; k <= n; k += k & (-k))
		{
			fwk[make_pair(i, k)] += v;
		}
	}
}

inline int qry(int i, int j)
{
	int ret = 0;
	for (; i; i -= i & (-i))
	{
		for (int k = j; k; k -= k & (-k))
		{
			ret += fwk[make_pair(i, k)];
		}
	}
	return ret;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	cin >> ar;
	int p = -1;
	for (int i = 0; i < n; i++)
	{
		if (ar[i] == '0')
		{
			if (p >= 0) s.insert({{p + 1, i}, 0});
			p = -1;
		}
		else if (p == -1) {p = i;}
	}
	if (p >= 0) {s.insert({{p + 1, n}, 0});}
	//for (auto x : s) cout << x.fst.fst << ", " << x.fst.snd << "\n";
	for (int i = 1; i <= q; i++)
	{
		string qq; cin >> qq;
		if (qq == "toggle")
		{
			int x; cin >> x; 
			if (ar[x - 1] == '1')
			{
				auto it = prev(s.upper_bound(make_pair(make_pair(x + 1, -1), -1)));
				ppi dt = *it; s.erase(it);
				upd(dt.fst.fst, n + 1 - dt.fst.snd, i - dt.snd);
				if (dt.fst.fst < x) s.insert(make_pair(make_pair(dt.fst.fst, x - 1), i));
				if (x < dt.fst.snd) s.insert(make_pair(make_pair(x + 1, dt.fst.snd), i));
				ar[x - 1] = '0';
			}
			else
			{
				int l = x, r = x;
				auto it = s.upper_bound(make_pair(make_pair(x + 1, -1), -1));
				if (it != s.end() && it -> fst.fst == r + 1)
				{
					r = it -> fst.snd;
					upd(it -> fst.fst, n + 1 - it -> fst.snd, i - it -> snd);
					it = s.erase(it);
				}
				if (it != s.begin())
				{
					it = prev(it);
					if (it -> fst.snd == l - 1)
					{
						l = it -> fst.fst;
						upd(it -> fst.fst, n + 1 - it -> fst.snd, i - it -> snd);
						it = s.erase(it);
					}
				}
				s.insert(make_pair(make_pair(l, r), i));
				ar[x - 1] = '1';
			}
		}
		else
		{
			int l, r, res = 0; cin >> l >> r; r--; 
			if (ar[l - 1] == '1')
			{
				auto it = prev(s.upper_bound(make_pair(make_pair(l + 1, -1), -1)));
				if (it -> fst.snd >= r) res += i - it -> snd;
			}
			//cout << res << "\n";
			res += qry(l, n + 1 - r);
			cout << res << "\n";
		}
	}
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20