Submission #1128979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128979		Alihan_8	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	4217 ms	304240 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define L(x)       x << 1
#define R(x)       x << 1 | 1

#define all(x) x.begin(), x.end()

const int N = 3e5 + 5;

struct Fenw{
	vector <int> fenw;
	
	int n;
	
	Fenw(int n = 0) : fenw(n + 1, 0), n(n) {}
	
	void upd(int i, int v){
		for (; i <= n; i += i & -i ) fenw[i] += v;
	}
	
	int get(int i){
		int cnt = 0;
		
		for (; i > 0; i -= i & -i ) cnt += fenw[i];
		
		return cnt;
	}
	
	int get(int l, int r){ return get(r) - get(l - 1); } 
};

vector <vector<int>> idx(N * 4);
vector <Fenw> seg(N * 4), cnt(N * 4);

int id(int v, int x){
	return lower_bound(all(idx[v]), x) - idx[v].begin() + 1;
}

int size(int v){ return (int)idx[v].size(); }

void add(int v, int l, int r, int p, int y){
	idx[v].push_back(y);
	
	if ( l == r ) return;
	
	int m = (l + r) / 2;
	
	if ( p <= m ) add(L(v), l, m, p, y);
	else add(R(v), m + 1, r, p, y);
}

void build(int v, int l, int r){
	sort(all(idx[v]));
	idx[v].resize(unique(all(idx[v])) - idx[v].begin());
	
	seg[v] = cnt[v] = Fenw(size(v));
	
	if ( l != r ){
		int m = (l + r) / 2;
		
		build(L(v), l, m);
		build(R(v), m + 1, r);
	}
}

void upd(int v, int l, int r, int p, int y, int d){
	seg[v].upd(id(v, y), d);
	
	if ( d <= 0 ) cnt[v].upd(id(v, y), 1);
	else cnt[v].upd(id(v, y), -1);
	
	if ( l == r ) return;
	
	int m = (l + r) / 2;
	
	if ( p <= m ) upd(L(v), l, m, p, y, d);
	else upd(R(v), m + 1, r, p, y, d);
}

int get(int v, int l, int r, int x, int y){
	if ( l > x ) return 0;
	
	if ( r <= x ) return seg[v].get(id(v, y), size(v));
	
	int m = (l + r) / 2;
	
	return get(L(v), l, m, x, y) + get(R(v), m + 1, r, x, y);
}

int get_neg(int v, int l, int r, int x, int y){
	if ( l > x ) return 0;
	
	if ( r <= x ) return cnt[v].get(id(v, y), size(v));
	
	int m = (l + r) / 2;
	
	return get_neg(L(v), l, m, x, y) + get_neg(R(v), m + 1, r, x, y);
}

signed main(){
	int n, q; cin >> n >> q;
	
	string s; cin >> s;
	
	for ( auto &u: s ) u -= '0';
	
	vector <array<int,3>> qu(q);
	
	for ( int i = 0; i < q; i++ ){
		string t; cin >> t;
		
		if ( t == "query" ){
			int l, r; cin >> l >> r;
			
			qu[i] = {0, l - 1, r - 2};
		} else{
			int p; cin >> p;
			
			qu[i] = {1, p - 1, -1};
		}
	}
	
	vector <pair<int,int>> stv;
	
	for ( int i = 0; i < n; i++ ){
		if ( s[i] == 0 ) continue;
		
		int j = i;
		
		while ( j + 1 < n && s[j + 1] ) j += 1;
		
		stv.push_back({i, j});
		i = j;
	}
	
	vector <vector<array<int,3>>> qry(q + 1);
	
	set <pair<int,int>> rng{{-2, -2}, {n + 1, n + 1}};
	
	for ( auto &x: stv ) rng.insert(x);
	
	auto insert = [&](int x, int i){
		auto it = rng.lower_bound({x, -1});
		auto [x1, y1] = *prev(it);
		auto [x2, y2] = *it;
		
		int l = x, r = x;
		
		if ( x + 1 == x2 ){
			qry[i].push_back({x2, y2, i});
			rng.erase({x2, y2}); r = y2;
		}
		
		if ( y1 + 1 == x ){
			qry[i].push_back({x1, y1, i});
			rng.erase({x1, y1}); l = x1;
		}
		
		qry[i].push_back({l, r, -i});
		rng.insert({l, r});
	};
	
	auto erase = [&](int x, int i){
		auto it = prev(rng.lower_bound({x + 1, -1}));
		auto [l, r] = *it;
		
		qry[i].push_back({l, r, i});
		rng.erase({l, r});
		
		if ( x != l ){
			qry[i].push_back({l, x - 1, -i});
			rng.insert({l, x - 1}); 
		}
		
		if ( x != r ){
			qry[i].push_back({x + 1, r, -i});
			rng.insert({x + 1, r});
		}
	};
	
	for ( int i = 0; i < q; i++ ){
		auto &[t, p, r] = qu[i];
		
		if ( t != 1 ) continue;
		
		if ( s[p] != 0 ){
			erase(p, i + 1);
		} else insert(p, i + 1);
		
		s[p] ^= 1;
	}
	
	for ( auto &[l, r]: stv ) add(1, 0, n - 1, l, r);
	for ( auto &v: qry ){
		for ( auto &[l, r, d]: v ) add(1, 0, n - 1, l, r);
	}
	
	build(1, 0, n - 1);
	
	for ( auto &[l, r]: stv ) upd(1, 0, n - 1, l, r, -0);
	
	for ( int i = 1; i <= q; i++ ){
		auto &[t, l, r] = qu[i - 1];
		
		if ( t == 1 ){
			for ( auto &[l, r, d]: qry[i] ){
				upd(1, 0, n - 1, l, r, d);
			}
		} else{
			cout << i * get_neg(1, 0, n - 1, l, r) + get(1, 0, n - 1, l, r) << '\n';
		}
	}
}

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