Submission #552054

#	Time	Username	Problem	Language	Result	Execution time	Memory
552054		cig32	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4989 ms	193648 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); }
int fastlog(int x) {
  return (x == 0 ? -1 : 32 - __builtin_clz(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
char ss[MAXN]; int n, q, t;
struct query {
  int x, y, v;
  bool is_qry;
  int ans;
  int id;
};
query ended[5 * MAXN], cnt[5 * MAXN], sum[5 * MAXN];
int e = 0, c = 0, s = 0;
int l[MAXN], r[MAXN];
set<pair<int, int> > all_segments;
unordered_map<int, int> simple_ended[MAXN], simple_cnt[MAXN], simple_sum[MAXN];
int global_id;
void insert_segment(int x, int y) {
  l[y] = x;
  r[x] = y;
  all_segments.insert({y, x});
  cnt[c++] = {x, y, 1, 0, 0, ++global_id};
  sum[s++] = {x, y, t, 0, 0, ++global_id};
  simple_cnt[x][y] += 1;
  simple_sum[x][y] += t;
}
void delete_segment(int x, int y) { 
  all_segments.erase({y, x});
  simple_ended[x][y] += t - simple_sum[x][y];
  ended[e++] = {x, y, t - simple_sum[x][y], 0, 0, ++global_id};
  cnt[c++] = {x, y, -simple_cnt[x][y], 0, 0, ++global_id};
  simple_cnt[x].erase(y);
  sum[s++] = {x, y, -simple_sum[x][y], 0, 0, ++global_id};
  simple_sum[x].erase(y);
  r[x] = l[y] = -1;
}
bool cmp2(query a, query b) {
  return a.id < b.id;
}
int bit[MAXN];
void add(int x, int v) {
  for(;x<MAXN;x+=x&-x) {
    bit[x] += v;
  }
}
int bit_sum(int x) {
  int sss = 0;
  for(;x;x-=x&-x) sss += bit[x];
  return sss;
}
int ct3 = 0;
int pt[MAXN];
void moshang_huakai(int array_id, int lb, int rb) {
  ++ct3;
  if(lb == rb) return;
  int mid = (lb + rb) >> 1;
  moshang_huakai(array_id, lb, mid);
  moshang_huakai(array_id, mid + 1, rb);
  pair<int, int> ll[mid - lb + 1], rr[rb - mid];
  for(int i=lb; i<=mid; i++) {
    if(array_id == 0) ll[i - lb] = {ended[i].x, i};
    else if(array_id == 1) ll[i - lb] = {cnt[i].x, i};
    else ll[i - lb] = {sum[i].x, i};
  }
  for(int i=mid+1; i<=rb; i++) {
    if(array_id == 0) rr[i - (mid + 1)] = {ended[i].x, i};
    else if(array_id == 1) rr[i - (mid + 1)] = {cnt[i].x, i};
    else rr[i - (mid + 1)] = {sum[i].x, i};
  }
  sort(ll, ll + mid - lb + 1);
  sort(rr, rr + rb - mid);
  int nxt = ll[0].second;
  int ti = 0;
  int upd[rb - mid + 2];
  int newidx = 0;
  for(int j=mid+1; j<=rb; j++) {
    int i = rr[j - (mid + 1)].second;
    if(ti < mid - lb + 1) {
      int xval, curx;
      if(array_id == 0) xval = ended[nxt].x, curx = ended[i].x;
      else if(array_id == 1) xval = cnt[nxt].x, curx = cnt[i].x;
      else xval = sum[nxt].x, curx = sum[i].x;
      while(ti < mid - lb + 1 && xval <= curx) {
        int yval, cury, ysum;
        if(array_id == 0) yval = ended[nxt].y, cury = ended[i].y, ysum = ended[nxt].v;
        else if(array_id == 1) yval = cnt[nxt].y, cury = cnt[i].y, ysum = cnt[nxt].v;
        else yval = sum[nxt].y, cury = sum[i].y, ysum = sum[nxt].v;
        add(yval + 1, ysum);
        pt[yval + 1] += ysum;
        //cout << "hi " << yval << " += " << ysum << ", " << array_id << "\n";
        upd[newidx++] = yval + 1;
        ti++;
        if(ti >= mid - lb + 1) break;
        nxt = ll[ti].second;
        if(array_id == 0) xval = ended[nxt].x;
        else if(array_id == 1) xval = cnt[nxt].x;
        else xval = sum[nxt].x;
      }
    }
    int cury;
    if(array_id == 0) cury = ended[i].y;
    else if(array_id == 1) cury = cnt[i].y;
    else cury = sum[i].y;
    if(array_id == 0) ended[i].ans += bit_sum(cury + 1);
    else if(array_id == 1) cnt[i].ans += bit_sum(cury + 1);
    else sum[i].ans += bit_sum(cury + 1);
  }
  for(int i=0; i<newidx; i++) {
    int x = upd[i];
    add(x, -pt[x]);
    pt[x] = 0;
  }
  
  
}
void solve(int tc) {
  t = 0;
  //n = 300000, q = 300000;
  cin >> n >> q;
  for(int i=1; i<=n; i++) {
    //ss[i] = char(rnd(0, 1) + '0'); 
    cin >> ss[i];
  }
  for(int i=0; i<=n+1; i++) l[i] = r[i] = -1;
  for(int i=1; i<=n; i++) {
    if(ss[i] == '1') {
      int j = i;
      while(j + 1 <= n && ss[j+1] == '1') ++j;
      insert_segment(i, j);
      i = j + 1;
    }
  }
  all_segments.insert({1e7, 1e7});
  vector<int> Times;
  while(q--) {
    ++t;
    string str;
    //str = (rnd(0, 1) ? "toggle" : "q");
    cin >> str;
    if(str == "toggle") {
      int i;
      //i = rnd(1, n);
      cin >> i;
      ss[i] = (ss[i] == '1' ? '0' : '1');
      if(ss[i] == '1') {
        if(l[i-1] != -1) {
          int sto = l[i-1];
          delete_segment(sto, i-1);
          insert_segment(sto, i);
        }
        else {
          insert_segment(i, i);
        }
        if(r[i+1] != -1) {
          int sto = r[i+1];
          int sto2 = l[i];
          delete_segment(l[i], i);
          delete_segment(i+1, sto);
          insert_segment(sto2, sto);
        }
      }
      else {
        auto it = all_segments.lower_bound({i, 0});
        pair<int, int> seg = *it;
        if(seg.first != 1e7 && seg.second <= i && i <= seg.first) {
          int ff = seg.second, ss = seg.first;
          delete_segment(ff, ss);
          if(ff < i) insert_segment(ff, i - 1);
          if(i < ss) insert_segment(i + 1, ss);
        }
      }
    }
    else {
      int a, b;
      cin >> a >> b;
      /*
      while(1) {
        a = rnd(1, n + 1);
        b = rnd(1, n + 1);
        if(a < b) break;
      }
      */
      b--;
      ended[e++] = {a, n, 0, 1, 0, ++global_id};
      ended[e++] = {a, b - 1, 0, 1, 0, ++global_id};
      cnt[c++] = {a, n, 0, 1, 0, ++global_id};
      cnt[c++] = {a, b - 1, 0, 1, 0, ++global_id};
      sum[s++] = {a, n, 0, 1, 0, ++global_id};
      sum[s++] = {a, b - 1, 0, 1, 0, ++global_id};
      //Ans = (if tcnt = 0: ended, else ended + t * tcnt - tsum)
      Times.push_back(t);
    }
  }
  moshang_huakai(0, 0, e - 1);
  moshang_huakai(1, 0, c - 1);
  moshang_huakai(2, 0, s - 1);
  vector<int> ended_ans, cnt_ans, sum_ans;
  for(int i=0; i<e; i++) {
    if(ended[i].is_qry == 1) {
      ended_ans.push_back(ended[i].ans);
    }
  }
  for(int i=0; i<c; i++) {
    if(cnt[i].is_qry == 1) {
      cnt_ans.push_back(cnt[i].ans);
    }
  }
  for(int i=0; i<s; i++) {
    if(sum[i].is_qry == 1) {
      sum_ans.push_back(sum[i].ans);
    }
  }
  assert(ended_ans.size() == cnt_ans.size() && cnt_ans.size() == sum_ans.size());
  int sz = ended_ans.size();
  for(int i=0; i<sz; i+=2) {
    int ans = ended_ans[i] - ended_ans[i + 1];
    int tcnt = cnt_ans[i] - cnt_ans[i + 1];
    int tsum = sum_ans[i] - sum_ans[i + 1];
    if(tcnt == 0) cout << ans << '\n';
    else cout << ans + Times[i >> 1] * tcnt - tsum << '\n';
  }
}
/*
5 1 11011 
query 1 2 
 
5 7 11011 
query 1 2 
query 1 2 
query 1 6 
query 3 4 
toggle 3 
query 3 4
query 1 6
*/
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
// I don't know geometry.

Compilation message (stderr)

street_lamps.cpp: In function 'void moshang_huakai(int, int, int)':
street_lamps.cpp:107:19: warning: variable 'cury' set but not used [-Wunused-but-set-variable]
  107 |         int yval, cury, ysum;
      |                   ^~~~

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