Submission #538597

#TimeUsernameProblemLanguageResultExecution timeMemory
538597hohohahaStreet Lamps (APIO19_street_lamps)C++14
100 / 100
3955 ms231784 KiB
#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) {
      |                                                                                   ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...