oj.uz

Submission #538595

# Submission time Handle Problem Language Result Execution time Memory
538595 2022-03-17T07:53:32 Z hohohaha Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4061 ms 424408 KB 
#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

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:82:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long 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(long long int, long long int, long long int)':
street_lamps.cpp:94:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long 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 'long long int bit::real_get(long long int, long long int)':
street_lamps.cpp:104:85: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15924 KB Output is correct
3 Correct 9 ms 15992 KB Output is correct
4 Correct 9 ms 15960 KB Output is correct
5 Correct 8 ms 16008 KB Output is correct
6 Correct 8 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 82448 KB Output is correct
2 Correct 860 ms 89832 KB Output is correct
3 Correct 1284 ms 111300 KB Output is correct
4 Correct 2736 ms 285012 KB Output is correct
5 Correct 2682 ms 289780 KB Output is correct
6 Correct 2763 ms 293900 KB Output is correct
7 Correct 1158 ms 136436 KB Output is correct
8 Correct 4061 ms 422360 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16596 KB Output is correct
2 Correct 11 ms 16596 KB Output is correct
3 Correct 11 ms 16596 KB Output is correct
4 Correct 13 ms 16852 KB Output is correct
5 Correct 2791 ms 260436 KB Output is correct
6 Correct 2739 ms 274920 KB Output is correct
7 Correct 2690 ms 294896 KB Output is correct
8 Correct 3891 ms 424408 KB Output is correct
9 Correct 208 ms 44840 KB Output is correct
10 Correct 225 ms 49344 KB Output is correct
11 Correct 235 ms 50036 KB Output is correct
12 Correct 1180 ms 135644 KB Output is correct
13 Correct 3936 ms 424304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16468 KB Output is correct
2 Correct 11 ms 16596 KB Output is correct
3 Correct 12 ms 16596 KB Output is correct
4 Correct 12 ms 16720 KB Output is correct
5 Correct 1893 ms 227456 KB Output is correct
6 Correct 2244 ms 262092 KB Output is correct
7 Correct 2805 ms 295176 KB Output is correct
8 Correct 3576 ms 364604 KB Output is correct
9 Correct 1018 ms 101172 KB Output is correct
10 Correct 878 ms 111760 KB Output is correct
11 Correct 980 ms 100912 KB Output is correct
12 Correct 846 ms 112040 KB Output is correct
13 Correct 1012 ms 101368 KB Output is correct
14 Correct 875 ms 111492 KB Output is correct
15 Correct 1147 ms 133012 KB Output is correct
16 Correct 4008 ms 421312 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 8 ms 15924 KB Output is correct
3 Correct 9 ms 15992 KB Output is correct
4 Correct 9 ms 15960 KB Output is correct
5 Correct 8 ms 16008 KB Output is correct
6 Correct 8 ms 15988 KB Output is correct
7 Correct 9 ms 16084 KB Output is correct
8 Correct 601 ms 82448 KB Output is correct
9 Correct 860 ms 89832 KB Output is correct
10 Correct 1284 ms 111300 KB Output is correct
11 Correct 2736 ms 285012 KB Output is correct
12 Correct 2682 ms 289780 KB Output is correct
13 Correct 2763 ms 293900 KB Output is correct
14 Correct 1158 ms 136436 KB Output is correct
15 Correct 4061 ms 422360 KB Output is correct
16 Correct 13 ms 16596 KB Output is correct
17 Correct 11 ms 16596 KB Output is correct
18 Correct 11 ms 16596 KB Output is correct
19 Correct 13 ms 16852 KB Output is correct
20 Correct 2791 ms 260436 KB Output is correct
21 Correct 2739 ms 274920 KB Output is correct
22 Correct 2690 ms 294896 KB Output is correct
23 Correct 3891 ms 424408 KB Output is correct
24 Correct 208 ms 44840 KB Output is correct
25 Correct 225 ms 49344 KB Output is correct
26 Correct 235 ms 50036 KB Output is correct
27 Correct 1180 ms 135644 KB Output is correct
28 Correct 3936 ms 424304 KB Output is correct
29 Correct 12 ms 16468 KB Output is correct
30 Correct 11 ms 16596 KB Output is correct
31 Correct 12 ms 16596 KB Output is correct
32 Correct 12 ms 16720 KB Output is correct
33 Correct 1893 ms 227456 KB Output is correct
34 Correct 2244 ms 262092 KB Output is correct
35 Correct 2805 ms 295176 KB Output is correct
36 Correct 3576 ms 364604 KB Output is correct
37 Correct 1018 ms 101172 KB Output is correct
38 Correct 878 ms 111760 KB Output is correct
39 Correct 980 ms 100912 KB Output is correct
40 Correct 846 ms 112040 KB Output is correct
41 Correct 1012 ms 101368 KB Output is correct
42 Correct 875 ms 111492 KB Output is correct
43 Correct 1147 ms 133012 KB Output is correct
44 Correct 4008 ms 421312 KB Output is correct
45 Correct 216 ms 55796 KB Output is correct
46 Correct 386 ms 59548 KB Output is correct
47 Correct 1284 ms 141920 KB Output is correct
48 Correct 2740 ms 285132 KB Output is correct
49 Correct 265 ms 51188 KB Output is correct
50 Correct 250 ms 50840 KB Output is correct
51 Correct 271 ms 52084 KB Output is correct
52 Correct 272 ms 56468 KB Output is correct
53 Correct 282 ms 56440 KB Output is correct
54 Correct 285 ms 56392 KB Output is correct