Submission #1031974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031974		pan	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	656 ms	58744 KiB

street_lamps

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
 
ll n, q, a, b;
ll MAXN = 300005;
 
struct qq
{
	ll type, l, r,  t;
	qq(ll a, ll b, ll c, ll d) {type = a, l = b, r = c, t= d;}
};
 
struct range
{
	ll l,  r,  t;
	range(ll a, ll b, ll c) {l = a, r = b, t = c;}
	bool operator< (const range & other) const
	{
		if (l!=other.l) return l< other.l;
		return r < other.r;
	}
};
 
bool compare(qq a, qq b)
{
	return a.l < b.l;
}
// BIT
vector<ll> fenwick(MAXN,0);
 
ll ps(ll i)
{
	if (i==0) return 0;
	ll sum=0;
	while (i>0)
	{
		sum+=fenwick[i];
		i-=i&(-i);
	}
	return sum;
}
void update(ll i, ll v)
{
	while (i<n+2)
	{
		fenwick[i]+=v;
		i+=i&(-i);
	}
}
 
 
ll query(ll l, ll r)
{
	if (l>r) return 0;
	return ps(r) - ps(l-1);
}
 
 
vector<qq> que[300005];
ll state[300005], ans[300005];
string s;
 
void dnc(ll from, ll to)
{
	if (from >= to) return;
	ll mid = (from+to)/2;
	vector<qq> cur;
	for (ll i=from; i<=mid; ++i) for (qq u: que[i]) if (u.type==0) cur.pb(u);
	for (ll i=mid+1; i<=to; ++i) for (qq u: que[i]) if (u.type) cur.pb(u);
	stable_sort(all(cur), compare);
	for (qq u: cur)
	{
		if (u.type==0) update(u.r, u.t);
		else ans[u.t] += query(u.r, n);
	}
	for (qq u: cur) if (u.type==0) update(u.r, -u.t);
	
	dnc(from, mid); dnc(mid+1, to);
	
	
}
 
int main()
{
	input2(n, q);
	cin >> s;
	ll l = LLONG_MAX;
	set<range> ds;
	for (ll i=1; i<=n; ++i) 
	{
		state[i] = s[i-1]-'0';
		if (l==LLONG_MAX && state[i]) l = i;
		if (state[i]==0) {if (l<i) ds.insert(range(l, i-1, 0)); l = LLONG_MAX;}
		else if (i==n) {if (l<=i) ds.insert(range(l, i, 0)); l = LLONG_MAX;}
	}
	//for (range x: ds) show3(x.l, x.r, x.t);
	fill(ans, ans+q+1, -1);
	for (ll i=1; i<=q; ++i)
	{
		//show(i);
		cin >> s;
		//show(s);
		if (s=="toggle") 
		{
			input(a);
			if (state[a]) // turn off
			{
				range it = *(--ds.lb(range(a+1, -1LL, 0)));
				que[i].pb(qq(0, it.l, it.r, i - it.t));
				ds.erase(--ds.lb(range(a+1, -1LL, 0)));
				if (it.l < a)ds.insert(range(it.l, a-1, i));
				if (it.r > a) ds.insert(range(a+1, it.r, i));
				
			}
			else // turn on
			{
				ll nowl = a, nowr = a;
				auto it = ds.lb(range(a+1, -1LL, 0));
				if (it!=ds.begin() && prev(it)->r == a-1)
				{
					--it;
					nowl = it->l;
					que[i].pb(qq(0, it->l, it->r, i-it->t));
					it = ds.erase(it);
				}
				if (it!=ds.end() && it->l <= a+1)
				{
					nowr = it->r;
					que[i].pb(qq(0, it->l, it->r, i-it->t));
					ds.erase(it);
				}
				ds.insert(range(nowl, nowr, i));
				
			}
			state[a] = !state[a];
		}
		else
		{
			input2(a, b);
			b--; 
			ans[i] = 0;
			auto it = ds.lb(range(a+1, -1LL, 0));
			//show(1);
			if (it!=ds.begin() && prev(it)-> r >= b && prev(it)->l <= a) ans[i] = i - prev(it)->t;
			//show(1);
			//show(ans[i]);
			que[i].pb(qq(1, a, b, i));
 
		}
	}
	//for (ll i=1; i<=q; ++i) {show(i); for (qq u: que[i]) show3(u.l, u.r, u.t);}
	dnc(0, q);
	for (ll i=1; i<=q; ++i) if (ans[i]!=-1) print(ans[i], '\n');
	
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:118:2: note: in expansion of macro 'input2'
  118 |  input2(n, q);
      |  ^~~~~~
street_lamps.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
street_lamps.cpp:138:4: note: in expansion of macro 'input'
  138 |    input(a);
      |    ^~~~~
street_lamps.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:172:4: note: in expansion of macro 'input2'
  172 |    input2(a, b);
      |    ^~~~~~

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