oj.uz

Submission #657347

# Submission time Handle Problem Language Result Execution time Memory
657347 2022-11-09T16:52:51 Z S2speed Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1296 ms 169064 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 3e5 + 17 , md = 1e9 + 7 , inf = 2e16;

struct fentree {
	
	ll sz;
	vector<ll> val;

	void init(ll n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(ll i , ll k){
		ll h = i;
		while(h < sz){
			val[h] += k;
			h |= (h + 1);
		}
		return;
	}

	void add(ll l , ll r , ll k){
		add(l , k); add(r , -k);
		return;
	}

	ll cal(ll i){
		ll h = i , res = 0;
		while(~h){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

};

struct node {

	ll sz;
	vector<ll> v;
	fentree ft;

	void pre(ll i){
		v.push_back(i);
		return;
	}

	void build(){
		sort(all(v));
		v.resize(distance(v.begin() , unique(all(v))));
		sz = sze(v);
		ft.init(sz);
		return;
	}

	void add(ll l , ll r , ll k){
		l = lower_bound(all(v) , l) - v.begin(); r = lower_bound(all(v) , r) - v.begin();
		ft.add(l , r , k);
		return;
	}

	ll cal(ll i){
		i = upper_bound(all(v) , i) - v.begin() - 1;
		return ft.cal(i);
	}

};

struct segtree2d {

	ll sz = 1;
	vector<node> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.resize(sz << 1);
		return;
	}

	void pre(ll l , ll r , pll k , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x].pre(k.first); val[x].pre(k.second);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pre(l , r , k , ln , lx , m); pre(l , r , k , rn , m , rx);
		return;
	}

	void pre(ll l , ll r , pll k){
		pre(l , r , k , 0 , 0 , sz);
		return;
	}

	void build(ll x , ll lx , ll rx){
		val[x].build();
		if(rx - lx == 1) return;
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(ln , lx , m); build(rn , m , rx);
		return;
	}

	void build(){
		build(0 , 0 , sz);
		return;
	}

	void add(ll l , ll r , plll k , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x].add(k.first.first , k.first.second , k.second);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		add(l , r , k , ln , lx , m); add(l , r , k , rn , m , rx);
		return;
	}

	void add(ll l , ll r , plll k){
		add(l , r , k , 0 , 0 , sz);
		return;
	}

	ll cal(ll i , ll j , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			return val[x].cal(j);
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		ll a;
		if(i < m){
			a = cal(i , j , ln , lx , m);
		} else {
			a = cal(i , j , rn , m , rx);
		}
		return a + val[x].cal(j);
	}

	ll cal(ll i , ll j){
		return cal(i , j , 0 , 0 , sz);
	}

};

struct segtree {

	ll sz = 1;
	vector<ll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , inf);
		return;
	}

	void build(ll k , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			val[x] = lx + k;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(k , ln , lx , m); build(k , rn , m , rx);
		return;
	}

	void build(ll k){
		build(k , 0 , 0 , sz);
		return;
	}

	void set(ll l , ll r , ll i , ll laz , ll x , ll lx , ll rx){
		if(laz != inf){
			val[x] = laz;
		}
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
			val[x] = i;
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		set(l , r , i , val[x] , ln , lx , m); set(l , r , i , val[x] , rn , m , rx);
		val[x] = inf;
		return;
	}

	void set(ll l , ll r , ll i){
		set(l , r , i , inf , 0 , 0 , sz);
		return;
	}

	ll cal(ll i , ll x , ll lx , ll rx){
		if(val[x] != inf) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		if(i < m) return cal(i , ln , lx , m);
		return cal(i , rn , m , rx);
	}

	ll cal(ll i){
		return cal(i , 0 , 0 , sz);
	}

	void clear(){
		sz = 1;
		val.clear();
		return;
	}

};

segtree2d st;
segtree lf , rt;
vector<pll> qu;
string s;
bitset<maxn> a;

void sefr_be_yek(ll i , ll t , bool p){
	ll lft = lf.cal(i) , rgt = rt.cal(i);
	lf.set(i + 1 , rgt + 1 , lft);
	rt.set(lft , i , rgt);
	if(p){
		st.pre(lft + 1 , i + 1 , {i + 1 , rgt + 1});
	} else {
//		if(t == 5){
//			cout<<lft + 1<<' '<<i + 1<<' '<<i<<' '<<rgt<<'\n';
//		}
		st.add(lft + 1 , i + 1 , {{i + 1 , rgt + 1} , -t});
	}
	return;
}

void yek_be_sefr(ll i , ll t , bool p){
	ll lft = lf.cal(i) , rgt = rt.cal(i);
	rt.set(lft , i , i);
	lf.set(i + 1 , rgt + 1 , i);
	if(p){
		st.pre(lft + 1 , i + 1 , {i + 1 , rgt + 1});
	} else {
		st.add(lft + 1 , i + 1 , {{i + 1 , rgt + 1} , t});
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	ll n , q;
	cin>>n>>q>>s;
	lf.init(n); rt.init(n);
	lf.build(-1); rt.build(1);
	st.init(n);
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1'){
			a[i] = true;
			sefr_be_yek(i , 0 , true);
		}
	}
	for(ll e = 1 ; e <= q ; e++){
		string t;
		cin>>t;
		if(t[0] == 't'){
			ll i;
			cin>>i; i--;
			qu.push_back({i , -1});
			if(a[i]){
				yek_be_sefr(i , e , true);
				a[i] = false;
			} else {
				sefr_be_yek(i , e , true);
				a[i] = true;
			}
			continue;
		}
		ll l , r;
		cin>>l>>r; l--; r--;
		qu.push_back({l , r});
	}
	lf.clear(); rt.clear();
	lf.init(n); rt.init(n);
	lf.build(-1); rt.build(1);
	st.build();
//	for(auto i : st.val[9].v){
//		cout<<i<<' ';
//	}
//	cout<<'\n';
	a.reset();
	for(ll i = 0 ; i < n ; i++){
		if(s[i] == '1'){
			a[i] = true;
			sefr_be_yek(i , 0 , false);
		}
	}
	ll t = 0;
	for(auto p : qu){
		t++;
		if(p.second == -1){
			ll i = p.first;
			if(a[i]){
				yek_be_sefr(i , t , false);
				a[i] = false;
			} else {
				sefr_be_yek(i , t , false);
				a[i] = true;
			}
			continue;
		}
		ll l = p.first , r = p.second;
		ll h = st.cal(l , r);
		if(a[l] == 1){
			if(rt.cal(l) >= r){
				h += t;
			}
		}
		cout<<h<<'\n';
	}
	return 0;
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 12884 KB Output is correct
2 Correct 243 ms 12776 KB Output is correct
3 Correct 332 ms 14612 KB Output is correct
4 Correct 853 ms 106972 KB Output is correct
5 Correct 922 ms 116600 KB Output is correct
6 Correct 927 ms 108196 KB Output is correct
7 Correct 227 ms 91112 KB Output is correct
8 Correct 1182 ms 162860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1036 ms 119016 KB Output is correct
6 Correct 992 ms 119868 KB Output is correct
7 Correct 935 ms 121408 KB Output is correct
8 Correct 1216 ms 168832 KB Output is correct
9 Correct 82 ms 7956 KB Output is correct
10 Correct 90 ms 11744 KB Output is correct
11 Correct 87 ms 11784 KB Output is correct
12 Correct 222 ms 96600 KB Output is correct
13 Correct 1251 ms 169064 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 481 ms 105056 KB Output is correct
6 Correct 695 ms 108980 KB Output is correct
7 Correct 890 ms 112816 KB Output is correct
8 Correct 1208 ms 117624 KB Output is correct
9 Correct 283 ms 19804 KB Output is correct
10 Correct 276 ms 19360 KB Output is correct
11 Correct 280 ms 19860 KB Output is correct
12 Correct 260 ms 19504 KB Output is correct
13 Correct 275 ms 20016 KB Output is correct
14 Correct 288 ms 19516 KB Output is correct
15 Correct 230 ms 96644 KB Output is correct
16 Correct 1296 ms 168796 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 208 ms 12884 KB Output is correct
9 Correct 243 ms 12776 KB Output is correct
10 Correct 332 ms 14612 KB Output is correct
11 Correct 853 ms 106972 KB Output is correct
12 Correct 922 ms 116600 KB Output is correct
13 Correct 927 ms 108196 KB Output is correct
14 Correct 227 ms 91112 KB Output is correct
15 Correct 1182 ms 162860 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1036 ms 119016 KB Output is correct
21 Correct 992 ms 119868 KB Output is correct
22 Correct 935 ms 121408 KB Output is correct
23 Correct 1216 ms 168832 KB Output is correct
24 Correct 82 ms 7956 KB Output is correct
25 Correct 90 ms 11744 KB Output is correct
26 Correct 87 ms 11784 KB Output is correct
27 Correct 222 ms 96600 KB Output is correct
28 Correct 1251 ms 169064 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 3 ms 596 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 481 ms 105056 KB Output is correct
34 Correct 695 ms 108980 KB Output is correct
35 Correct 890 ms 112816 KB Output is correct
36 Correct 1208 ms 117624 KB Output is correct
37 Correct 283 ms 19804 KB Output is correct
38 Correct 276 ms 19360 KB Output is correct
39 Correct 280 ms 19860 KB Output is correct
40 Correct 260 ms 19504 KB Output is correct
41 Correct 275 ms 20016 KB Output is correct
42 Correct 288 ms 19516 KB Output is correct
43 Correct 230 ms 96644 KB Output is correct
44 Correct 1296 ms 168796 KB Output is correct
45 Correct 98 ms 8920 KB Output is correct
46 Correct 141 ms 9032 KB Output is correct
47 Correct 429 ms 35952 KB Output is correct
48 Correct 878 ms 111604 KB Output is correct
49 Correct 87 ms 11848 KB Output is correct
50 Correct 83 ms 11764 KB Output is correct
51 Correct 94 ms 11944 KB Output is correct
52 Correct 98 ms 12432 KB Output is correct
53 Correct 89 ms 12332 KB Output is correct
54 Correct 90 ms 12392 KB Output is correct