Submission #538585

#	Time	Username	Problem	Language	Result	Execution time	Memory
538585		hohohaha	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5080 ms	524288 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define	fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
#define int long long

const int maxn = 5e5 + 5; 
int n, q; 
char c[maxn]; 
string tp[maxn];
int id[maxn]; 
bool state[maxn]; 	

struct it { 
	vi mn, mx; // min, max of off ones
	it (int len= 1) {
		mn = vi(4 * len + 5, n); 
		mx = vi(4 * len + 5, 0); 
		build(1, 1, len); 
	}
	void build(int u, int l, int r) { 
		if(l == r) mn[u] = mx[u] = l; 
		else {
			int mid = l + r >> 1; 
			build(u << 1, l, mid); 
			build(u << 1 | 1, mid + 1, r); 
			mn[u] = l; 
			mx[u] = r;
		}
	}
	void sett(int u, int l, int r, int p, bool on) { 
		if(l > p or p > r) return; 
		if(l == r) { 
			mn[u] = !on? p: n; 
			mx[u] = !on? p: 0;
		}
		else { 
			int mid = l + r >> 1; 
			sett(u << 1, l, mid, p, on); 
			sett(u << 1 | 1, mid + 1, r , p, on); 
			mn[u] = min(mn[u << 1], mn[u << 1 | 1]);
			mx[u] = max(mx[u << 1], mx[u << 1 | 1]); 
		}
	 }
	
	int get_min(int u, int l, int r, int ll, int rr) { 
		if(l > rr or ll > r) return n; 
		if(ll <= l and r <= rr) return mn[u]; 
		int mid = l + r >> 1; 
		return min(get_min(u << 1, l, mid, ll, rr), get_min(u << 1 | 1, mid + 1, r, ll, rr)); 
	}
	int get_max(int u, int l, int r, int ll, int rr) { 
		if(l > rr or ll > r) return 0; 
		if(ll <= l and r <= rr) return mx[u]; 
		int mid = l + r >> 1; 
		return max(get_max(u << 1, l, mid, ll, rr), get_max(u << 1 | 1, mid + 1, r, ll, rr)); 
	}
} IT; 

struct bit { 
	vector<unordered_map<int, int> > sum;
	bit(int len = 0) { 
		sum.resize(len + 10); 
	}
	
	void add(int x, int y, int v) { 
		for(int i = x; i < sum.size(); i += i & -i) {
			for(int j = y; j > 0; j -= j & -j) { 
				sum[i][j] += v; 
			}
		}
	}
	int get(int x, int y) {
		int r = 0; 
		for(int i = x; i > 0; i -= i & -i) { 
			for(int j = y; j < sum.size(); j += j & -j) { 
				r += sum[i][j]; 
			}
		}
		return r;
	}
} BIT; 

void turn_on(int i, int t) { 
//	cout << "ON: " << i << endl; 
	int L = IT.get_max(1, 1, n - 1, 1, i - 1) + 1; 
	int R = IT.get_min(1, 1, n - 1, i + 1, n - 1) - 1; 
//	cout << "continuous: " <<  L << sp << R << endl;
	IT.sett(1, 1, n - 1, i, 1); 
	BIT.add(L, R + 1, -t); 
	BIT.add(L, i, t); 
	BIT.add(i + 1, R + 1, t); 
	state[i] = 1; 
}

void turn_off(int i, int t) { 
//	cout << "OFF: " << i << endl; 
	int L = IT.get_max(1, 1, n - 1, 1, i - 1) + 1; 
	int R = IT.get_min(1, 1, n - 1, i + 1, n - 1) - 1; 
	IT.sett(1, 1, n - 1, i, 0);
	BIT.add(L, R + 1, t); 
	BIT.add(L, i, -t); 
	BIT.add(i + 1, R + 1, -t); 
	state[i] = 0; 
}

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cin >> n >> q;
	n++;  
	IT = it(n - 1); 
	BIT = bit(n); 
	fori(i, 1, n - 1) { 
		cin >> c[i]; 
		if(c[i] == '1') turn_on(i, 0); 
	}
	fori(i, 1, q) { 
		cin >> tp[i]; 
		if(tp[i] == "toggle") { 
			cin >> id[i];
			if(state[id[i]] == 0) turn_on(id[i], i); 
			else if(state[id[i]] == 1) turn_off(id[i], i); 
		}
		else { 
			int l, r; 
			cin >> l >> r; 
			int cur = BIT.get(l, r); 
			if(IT.get_min(1, 1, n - 1, l, r - 1) >= r) cout << cur + i; 
			else cout << cur;
			cout << endl;  
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void it::build(long long int, long long int, long long int)':
street_lamps.cpp:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |    int mid = l + r >> 1;
      |              ~~^~~
street_lamps.cpp: In member function 'void it::sett(long long int, long long int, long long int, long long int, bool)':
street_lamps.cpp:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |    int mid = l + r >> 1;
      |              ~~^~~
street_lamps.cpp: In member function 'long long int it::get_min(long long int, long long int, long long int, long long int, long long int)':
street_lamps.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In member function 'long long int it::get_max(long long int, long long int, long long int, long long int, long long int)':
street_lamps.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In member function 'void bit::add(long long int, long long int, long long int)':
street_lamps.cpp:75:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::unordered_map<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = x; i < sum.size(); i += i & -i) {
      |                  ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'long long int bit::get(long long int, long long int)':
street_lamps.cpp:84:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::unordered_map<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int j = y; j < sum.size(); j += j & -j) {
      |                   ~~^~~~~~~~~~~~

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