Submission #255573

#	Time	Username	Problem	Language	Result	Execution time	Memory
255573		Berted	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1878 ms	72364 KiB

street_lamps

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;

vector<int> coord[300001];
vector<int> fwk[300001];
ppi op[300002];
int n, q; 
string ar, ar2;
set<ppi> s, s2;

namespace fastIO
{
	char outString[64];
	//inline int getchar_unlocked() {return getchar();}
	//inline void putchar_unlocked(int x) {putchar(x);}
	inline int charInput() {return getchar_unlocked();}
	inline void charOutput(int x) {putchar_unlocked(x);}
	inline bool isNum(int c) {return '0' <= c && c <= '9';}
	inline int intInput()
	{
		int c = 0, ret = 0; bool neg = 0;
		while (!isNum(c)) 
		{
			c = getchar_unlocked();
			if (c == '-') {neg = 1;}
		}
		while (isNum(c)) {ret = ret * 10 + c - '0'; c = getchar_unlocked();}
		return (neg) ? -ret : ret;
	}
	inline void intOutput(int x)
	{
		int ss = 0;
		while (x) {outString[ss++] = x % 10 + '0'; x /= 10;}
		if (!ss) outString[ss++] = '0';
		for (int i = ss - 1; i >= 0; i--) putchar_unlocked(outString[i]);
	}
	inline string strInput()
	{
		string s = "";
		char c = getchar_unlocked();
		while (c == '\n' || c == ' ') {c = getchar_unlocked();}
		while (c != '\n' && c != ' ')
		{
			s.push_back(c);
			c = getchar_unlocked();
		}
		return s;
	}
	inline void strOutput(string s)
	{
		for (auto &c : s) putchar_unlocked(c);
	}
}

inline void preprocu(int i, int j)
{
	for (; i <= n; i += i & (-i)) {coord[i].push_back(j);}
}

inline void preprocr(int i, int j)
{
	for (; i; i -= i & (-i)) {coord[i].push_back(j);}
}


inline void proc()
{
	for (int i = 1; i <= n; i++)
	{
		sort(coord[i].begin(), coord[i].end());
		coord[i].resize(distance(coord[i].begin(), unique(coord[i].begin(), coord[i].end())));
		fwk[i].assign(coord[i].size(), 0);
	}
}

inline void upd(int i, int j, int v)
{
	for (; i <= n; i += i & (-i))
	{
		int it = lower_bound(coord[i].begin(), coord[i].end(), j) - coord[i].begin();
		for (int k = it; k < coord[i].size(); k += k & (-k))
		{
			fwk[i][k] += v;
		}
	}
}

inline int qry(int i, int j)
{
	int ret = 0;
	for (; i; i -= i & (-i))
	{
		int it = lower_bound(coord[i].begin(), coord[i].end(), j) - coord[i].begin();
		for (int k = it; k; k -= k & (-k)) {ret += fwk[i][k];}
	}
	return ret;
}

int main()
{
	// ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	n = fastIO::intInput();
	q = fastIO::intInput();
	ar = fastIO::strInput();
	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;}
		coord[i + 1].push_back(0);
	}
	if (p >= 0) {s.insert({{p + 1, n}, 0});}
	s2 = s; ar2 = ar;
	for (int i = 1; i <= q; i++)
	{
		string qq = fastIO::strInput();
		if (qq == "toggle")
		{
			int x; x = fastIO::intInput();
			op[i].snd = 0; op[i].fst.fst = x;
			if (ar2[x - 1] == '1')
			{
				auto it = prev(s2.upper_bound(make_pair(make_pair(x + 1, -1), -1)));
				ppi dt = *it; s2.erase(it);
				preprocu(dt.fst.fst, n + 1 - dt.fst.snd);
				if (dt.fst.fst < x) s2.insert(make_pair(make_pair(dt.fst.fst, x - 1), i));
				if (x < dt.fst.snd) s2.insert(make_pair(make_pair(x + 1, dt.fst.snd), i));
				ar2[x - 1] = '0';
			}
			else
			{
				int l = x, r = x;
				auto it = s2.upper_bound(make_pair(make_pair(x + 1, -1), -1));
				if (it != s2.end() && it -> fst.fst == r + 1)
				{
					r = it -> fst.snd;
					preprocu(it -> fst.fst, n + 1 - it -> fst.snd);
					it = s2.erase(it);
				}
				if (it != s2.begin())
				{
					it = prev(it);
					if (it -> fst.snd == l - 1)
					{
						l = it -> fst.fst;
						preprocu(it -> fst.fst, n + 1 - it -> fst.snd);
						it = s2.erase(it);
					}
				}
				s2.insert(make_pair(make_pair(l, r), i));
				ar2[x - 1] = '1';
			}
		}
		else
		{
			op[i].snd = 1;
			int l, r; 
			l = fastIO::intInput(); 
			r = fastIO::intInput();
			r--; 
			op[i].fst = {l, r};
			preprocr(l, n + 1 - r);
		}
	}
	proc();
	for (int i = 1; i <= q; i++)
	{
		if (op[i].snd == 0)
		{
			int x; x = op[i].fst.fst;
			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;
			l = op[i].fst.fst; r = op[i].fst.snd;
			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);
			fastIO::intOutput(res);
			fastIO::charOutput('\n');
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void upd(int, int, int)':
street_lamps.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k = it; k < coord[i].size(); k += k & (-k))
                    ~~^~~~~~~~~~~~~~~~~

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