Submission #538597

#	Time	Username	Problem	Language	Result	Execution time	Memory
538597		hohohaha	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3955 ms	231784 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]; 	
int ans[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<pair<ii, ii> > qrs; 
	vector<vi> vals; 
	vector<vi> sum; 	
	vector<int> res; 
	
	bit(int len = 0) { 
		vals.resize(len + 10); 
		sum.resize(len + 10); 
	}
	
	void add(int x, int y, int v) { 
		qrs.eb(ii(0, v), ii(x, y)); 
		for(int i = x; i < sum.size(); i += i & -i) {
			vals[i].eb(y); 
		}
	}
	void get(int x, int y) {
		qrs.eb(ii(1, 0), ii(x, y)); 
		for(int i = x; i > 0; i -= i & -i) { 
			vals[i].eb(y); 
		}
	}
	
	void real_add(int x, int y, int v) { 
		for(int i = x; i < sum.size(); i += i &-i) { 
			for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j > 0; j -= j & -j) { 
				sum[i][j] += v; 
			}
		}
	}
	
	int real_get(int x, int y) { 
		int r = 0; 
		for(int i = x; i > 0; i -= i &-i) { 
			for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j < sum[i].size(); j += j & -j) { 
				r += sum[i][j]; 
			}
		}
		return r; 
	}
	
	
	void process() { 
		fori(i, 1, sum.size() - 1) { 	
			sort(begin(vals[i]),end(vals[i])); 
			sum[i].resize(vals[i].size() + 5); 
		}
		for(auto t: qrs) {
			if(t.fi.fi == 0) { 
				int v=  t.fi.se; 
				int x = t.se.fi, y = t.se.se;
				real_add(x, y, v);  
			}
			else { 
				int x = t.se.fi, y = t.se.se; 
				res.eb(real_get(x, y)); 
			}
		}
	}
} BIT; 
 
void turn_on(int i, int t) { 
	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, 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) { 
	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; 
			BIT.get(l, r); 
			if(IT.get_min(1, 1, n - 1, l, r - 1) >= r) ans[i] += i; 
		}
	}
	BIT.process(); 
	auto temp = BIT.res; 
//	cout << temp.size() << endl; 
	int pt = 0; 
	fori(i, 1, q) { 
		if(tp[i] == "query") { 
			ans[i] += temp[pt++]; 
			cout << ans[i] << endl; 
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void it::build(int, int, 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(int, int, int, 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 'int it::get_min(int, int, int, int, int)':
street_lamps.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In member function 'int it::get_max(int, int, int, int, 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(int, int, int)':
street_lamps.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i = x; i < sum.size(); i += i & -i) {
      |                  ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'void bit::real_add(int, int, int)':
street_lamps.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int i = x; i < sum.size(); i += i &-i) {
      |                  ~~^~~~~~~~~~~~
street_lamps.cpp: In member function 'int bit::real_get(int, int)':
street_lamps.cpp:104:85: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    for(int j = lower_bound(begin(vals[i]), end(vals[i]), y) - begin(vals[i]) + 1; j < sum[i].size(); j += j & -j) {
      |                                                                                   ~~^~~~~~~~~~~~~~~

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