Submission #379544

#	Time	Username	Problem	Language	Result	Execution time	Memory
379544		AriaH	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	3793 ms	218100 KiB

street_lamps

/** I can do this all day **/
 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
 
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
 
ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
 
char C[N];
 
string s;
 
int n, q, tp[N], fir[N], sec[N], checking;
 
vector < ll > vec[N], F[2][N]; /// F[0][i] -> sigma -l + r, F[1][i] -> tedad l haye bedune r
 
set < pii > st;
 
void pre_add(int i, int r) { for(; i <= n; i += i & -i) { vec[i].push_back(r); } }
 
void prep()
{ 
	for(int i = 0; i <= n; i ++)
	{ 
		vec[i].push_back(-mod);
		sort(all(vec[i]));
		vec[i].resize(unique(all(vec[i])) - vec[i].begin());
		F[0][i].resize(SZ(vec[i]) + 5, 0);
		F[1][i].resize(SZ(vec[i]) + 5, 0);
	}
}
 
void pre_ins(int i)
{
	if(st.empty()) { st.insert(Mp(i, i)); pre_add(i, i); return; }
	auto it = st.lower_bound(Mp(i, 0));
	if(it == st.end())
	{
		it --; pii cu = *it;
		if(cu.S == i - 1) { st.erase(it); cu.S ++; st.insert(cu); pre_add(cu.F, cu.S); }
		else st.insert(Mp(i, i)), pre_add(i, i);
		return;
	}
	pii R = *it;
	if(it == st.begin())
	{
		if(R.F == i + 1) { st.erase(R); R.F --; st.insert(R); pre_add(R.F, R.S); }
		else st.insert(Mp(i, i)), pre_add(i, i);
		return;
	}
	auto it2 = it; it2 --; pii L = *it2;
	if(L.S + 1 == R.F - 1) { st.erase(L); st.erase(R); st.insert(Mp(L.F, R.S)); pre_add(L.F, R.S); }
	else if(L.S + 1 == i) { st.erase(L); st.insert(Mp(L.F, i)); pre_add(L.F, i); }
	else if(R.F == i + 1) { st.erase(R); st.insert(Mp(i, R.S)); pre_add(i, R.S); }
	else st.insert(Mp(i, i)), pre_add(i, i);
}
 
void pre_del(int i)
{
	auto it = st.upper_bound(Mp(i, mod));
	it --;
	pii cu = *it;
	st.erase(it);
	if(cu.F < i && i < cu.S)
	{
		st.insert(Mp(cu.F, i - 1)); pre_add(cu.F, i - 1);
		st.insert(Mp(i + 1, cu.S)); pre_add(i + 1, cu.S);
	}
	else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), pre_add(i + 1, cu.S);
	else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), pre_add(cu.F, i - 1);
}
 
void add(int i, int r, int Tp, int x)
{
	for(; i <= n; i += i & -i)
	{
		int id = lower_bound(all(vec[i]), r) - vec[i].begin();
		for(int j = id; j < SZ(vec[i]); j += j & -j)
		{
			F[Tp][i][j] += x;
		}
	}
}
 
ll get(int i, int r, int Tp)
{
	ll ret = 0;
	for(; i; i -= i & -i)
	{
		int id = lower_bound(all(vec[i]), r) - vec[i].begin();
		for(int j = SZ(vec[i]) - 1; j; j -= j & -j)
		{
			ret += F[Tp][i][j];
		}
		for(int j = id - 1; j; j -= j & -j)
		{
			ret -= F[Tp][i][j];
		}
	}
	return ret;
}
 
inline void _add(int l, int r, int t)
{
	add(l, r, 0, -t);
	add(l, r, 1, 1);
}
 
inline void _del(int l, int r, int t)
{
	add(l, r, 0, t);
	add(l, r, 1, -1);
}
 
void ins(int i, int t)
{
	if(st.empty()) { st.insert(Mp(i, i)); _add(i, i, t); return; }
	auto it = st.lower_bound(Mp(i, 0));
	if(it == st.end())
	{
		it --; pii cu = *it;
		if(cu.S == i - 1) { st.erase(it); _del(cu.F, cu.S, t); cu.S ++; st.insert(cu); _add(cu.F, cu.S, t); }
		else st.insert(Mp(i, i)), _add(i, i, t);
		return;
	}
	pii R = *it;
	if(it == st.begin())
	{
		if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); R.F --; st.insert(R); _add(R.F, R.S, t); }
		else st.insert(Mp(i, i)), _add(i, i, t);
		return;
	}
	auto it2 = it; it2 --; pii L = *it2;
	if(L.S + 1 == R.F - 1) { st.erase(L); _del(L.F, L.S, t); st.erase(R); _del(R.F, R.S, t); st.insert(Mp(L.F, R.S)); _add(L.F, R.S, t); }
	else if(L.S + 1 == i) { st.erase(L); _del(L.F, L.S, t); st.insert(Mp(L.F, i)); _add(L.F, i, t); }
	else if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); st.insert(Mp(i, R.S)); _add(i, R.S, t); }
	else st.insert(Mp(i, i)), _add(i, i, t);
 
}
 
void del(int i, int t)
{
	auto it = st.upper_bound(Mp(i, mod));
	it --;
	pii cu = *it;
	_del(cu.F, cu.S, t);
	st.erase(cu);
	if(cu.F < i && i < cu.S)
	{
		st.insert(Mp(cu.F, i - 1)); _add(cu.F, i - 1, t);
		st.insert(Mp(i + 1, cu.S)); _add(i + 1, cu.S, t);
	}
	else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), _add(i + 1, cu.S, t);
	else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), _add(cu.F, i - 1, t);
 
}
 
int main()
{
	scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
	string t = s;
	set < pii > goshad;
	int last = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(s[i] == '0')
		{
			if(last == i - 1) { last = i; continue; }
			pre_add(last + 1, i - 1); st.insert(Mp(last + 1, i - 1)); goshad.insert(Mp(last + 1, i - 1));
			last = i;
		}
	}
	if(last != n) { pre_add(last + 1, n); st.insert(Mp(last + 1, n)); goshad.insert(Mp(last + 1, n)); }	
	for(int i = 1; i <= q; i ++)
	{
		scanf("%s%d", C, &fir[i]);
		if(C[0] == 't') tp[i] = 1;
		else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
		if(tp[i] == 1)
		{
			if(s[fir[i]] == '0') pre_ins(fir[i]), s[fir[i]] = '1';
			else pre_del(fir[i]), s[fir[i]] = '0';
		}
		else
		{
			pre_add(fir[i], sec[i]);
		}
	}
	prep();
	st = goshad;
	for(auto x : st)
	{
		_add(x.F, x.S, 0);
	}
	s = t;
	for(int i = 1; i <= q; i ++)
	{
		if(tp[i] == 1)
		{
			if(s[fir[i]] == '0')
			{
				s[fir[i]] = '1';
				ins(fir[i], i);
			}
			else
			{
				s[fir[i]] = '0';
				del(fir[i], i);
			}
		}
		else
		{
			ll tot = 1ll * i * get(fir[i], sec[i], 1) + get(fir[i], sec[i], 0);
			printf("%lld\n", tot);
		}
	}
    return 0;
}
 
/** tesy corney cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  178 |  scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  194 |   scanf("%s%d", C, &fir[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:196:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |   else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
      |                   ~~~~~^~~~~~~~~~~~~~~

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