oj.uz

Submission #1031974

# Submission time Handle Problem Language Result Execution time Memory
1031974 2024-07-23T09:16:14 Z pan Street Lamps (APIO19_street_lamps) C++17
100 / 100
 656 ms 58744 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 42592 KB Output is correct
2 Correct 485 ms 42952 KB Output is correct
3 Correct 490 ms 43612 KB Output is correct
4 Correct 598 ms 51792 KB Output is correct
5 Correct 633 ms 52692 KB Output is correct
6 Correct 573 ms 58528 KB Output is correct
7 Correct 387 ms 45956 KB Output is correct
8 Correct 403 ms 45948 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9816 KB Output is correct
5 Correct 503 ms 44268 KB Output is correct
6 Correct 654 ms 50236 KB Output is correct
7 Correct 656 ms 52604 KB Output is correct
8 Correct 449 ms 45948 KB Output is correct
9 Correct 185 ms 33520 KB Output is correct
10 Correct 204 ms 39896 KB Output is correct
11 Correct 205 ms 38800 KB Output is correct
12 Correct 420 ms 45796 KB Output is correct
13 Correct 419 ms 45952 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 505 ms 51852 KB Output is correct
6 Correct 641 ms 58744 KB Output is correct
7 Correct 614 ms 58416 KB Output is correct
8 Correct 623 ms 50964 KB Output is correct
9 Correct 460 ms 51404 KB Output is correct
10 Correct 415 ms 42268 KB Output is correct
11 Correct 422 ms 51296 KB Output is correct
12 Correct 431 ms 42184 KB Output is correct
13 Correct 445 ms 51348 KB Output is correct
14 Correct 386 ms 42204 KB Output is correct
15 Correct 415 ms 45988 KB Output is correct
16 Correct 392 ms 45948 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 447 ms 42592 KB Output is correct
9 Correct 485 ms 42952 KB Output is correct
10 Correct 490 ms 43612 KB Output is correct
11 Correct 598 ms 51792 KB Output is correct
12 Correct 633 ms 52692 KB Output is correct
13 Correct 573 ms 58528 KB Output is correct
14 Correct 387 ms 45956 KB Output is correct
15 Correct 403 ms 45948 KB Output is correct
16 Correct 5 ms 9820 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 5 ms 9816 KB Output is correct
20 Correct 503 ms 44268 KB Output is correct
21 Correct 654 ms 50236 KB Output is correct
22 Correct 656 ms 52604 KB Output is correct
23 Correct 449 ms 45948 KB Output is correct
24 Correct 185 ms 33520 KB Output is correct
25 Correct 204 ms 39896 KB Output is correct
26 Correct 205 ms 38800 KB Output is correct
27 Correct 420 ms 45796 KB Output is correct
28 Correct 419 ms 45952 KB Output is correct
29 Correct 5 ms 9816 KB Output is correct
30 Correct 5 ms 9820 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 5 ms 9820 KB Output is correct
33 Correct 505 ms 51852 KB Output is correct
34 Correct 641 ms 58744 KB Output is correct
35 Correct 614 ms 58416 KB Output is correct
36 Correct 623 ms 50964 KB Output is correct
37 Correct 460 ms 51404 KB Output is correct
38 Correct 415 ms 42268 KB Output is correct
39 Correct 422 ms 51296 KB Output is correct
40 Correct 431 ms 42184 KB Output is correct
41 Correct 445 ms 51348 KB Output is correct
42 Correct 386 ms 42204 KB Output is correct
43 Correct 415 ms 45988 KB Output is correct
44 Correct 392 ms 45948 KB Output is correct
45 Correct 254 ms 30424 KB Output is correct
46 Correct 265 ms 30832 KB Output is correct
47 Correct 350 ms 32724 KB Output is correct
48 Correct 573 ms 51836 KB Output is correct
49 Correct 267 ms 40800 KB Output is correct
50 Correct 214 ms 40816 KB Output is correct
51 Correct 211 ms 41064 KB Output is correct
52 Correct 247 ms 41232 KB Output is correct
53 Correct 241 ms 41264 KB Output is correct
54 Correct 241 ms 41380 KB Output is correct