oj.uz

Submission #552054

# Submission time Handle Problem Language Result Execution time Memory
552054 2022-04-22T10:19:46 Z cig32 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4989 ms 193648 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51948 KB Output is correct
2 Correct 30 ms 52052 KB Output is correct
3 Correct 31 ms 52052 KB Output is correct
4 Correct 30 ms 52096 KB Output is correct
5 Correct 30 ms 52052 KB Output is correct
6 Correct 30 ms 52052 KB Output is correct
7 Correct 32 ms 52128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3457 ms 107620 KB Output is correct
2 Correct 3376 ms 108072 KB Output is correct
3 Correct 3330 ms 110792 KB Output is correct
4 Correct 3650 ms 171576 KB Output is correct
5 Correct 4606 ms 174008 KB Output is correct
6 Correct 3617 ms 174784 KB Output is correct
7 Correct 2735 ms 117268 KB Output is correct
8 Correct 2783 ms 117144 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 52496 KB Output is correct
2 Correct 39 ms 52484 KB Output is correct
3 Correct 38 ms 52448 KB Output is correct
4 Correct 36 ms 52252 KB Output is correct
5 Correct 4578 ms 184132 KB Output is correct
6 Correct 4989 ms 193648 KB Output is correct
7 Correct 4501 ms 177684 KB Output is correct
8 Correct 2784 ms 121556 KB Output is correct
9 Correct 1616 ms 101568 KB Output is correct
10 Correct 1754 ms 109156 KB Output is correct
11 Correct 1716 ms 109032 KB Output is correct
12 Correct 2778 ms 121548 KB Output is correct
13 Correct 2748 ms 121660 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 52308 KB Output is correct
2 Correct 36 ms 52400 KB Output is correct
3 Correct 37 ms 52368 KB Output is correct
4 Correct 38 ms 52416 KB Output is correct
5 Correct 3036 ms 147004 KB Output is correct
6 Correct 3304 ms 162132 KB Output is correct
7 Correct 3669 ms 174468 KB Output is correct
8 Correct 4050 ms 186908 KB Output is correct
9 Correct 3391 ms 105792 KB Output is correct
10 Correct 3495 ms 103452 KB Output is correct
11 Correct 3451 ms 105816 KB Output is correct
12 Correct 3504 ms 103340 KB Output is correct
13 Correct 3453 ms 105852 KB Output is correct
14 Correct 3515 ms 103436 KB Output is correct
15 Correct 2764 ms 117240 KB Output is correct
16 Correct 2853 ms 117072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51948 KB Output is correct
2 Correct 30 ms 52052 KB Output is correct
3 Correct 31 ms 52052 KB Output is correct
4 Correct 30 ms 52096 KB Output is correct
5 Correct 30 ms 52052 KB Output is correct
6 Correct 30 ms 52052 KB Output is correct
7 Correct 32 ms 52128 KB Output is correct
8 Correct 3457 ms 107620 KB Output is correct
9 Correct 3376 ms 108072 KB Output is correct
10 Correct 3330 ms 110792 KB Output is correct
11 Correct 3650 ms 171576 KB Output is correct
12 Correct 4606 ms 174008 KB Output is correct
13 Correct 3617 ms 174784 KB Output is correct
14 Correct 2735 ms 117268 KB Output is correct
15 Correct 2783 ms 117144 KB Output is correct
16 Correct 39 ms 52496 KB Output is correct
17 Correct 39 ms 52484 KB Output is correct
18 Correct 38 ms 52448 KB Output is correct
19 Correct 36 ms 52252 KB Output is correct
20 Correct 4578 ms 184132 KB Output is correct
21 Correct 4989 ms 193648 KB Output is correct
22 Correct 4501 ms 177684 KB Output is correct
23 Correct 2784 ms 121556 KB Output is correct
24 Correct 1616 ms 101568 KB Output is correct
25 Correct 1754 ms 109156 KB Output is correct
26 Correct 1716 ms 109032 KB Output is correct
27 Correct 2778 ms 121548 KB Output is correct
28 Correct 2748 ms 121660 KB Output is correct
29 Correct 36 ms 52308 KB Output is correct
30 Correct 36 ms 52400 KB Output is correct
31 Correct 37 ms 52368 KB Output is correct
32 Correct 38 ms 52416 KB Output is correct
33 Correct 3036 ms 147004 KB Output is correct
34 Correct 3304 ms 162132 KB Output is correct
35 Correct 3669 ms 174468 KB Output is correct
36 Correct 4050 ms 186908 KB Output is correct
37 Correct 3391 ms 105792 KB Output is correct
38 Correct 3495 ms 103452 KB Output is correct
39 Correct 3451 ms 105816 KB Output is correct
40 Correct 3504 ms 103340 KB Output is correct
41 Correct 3453 ms 105852 KB Output is correct
42 Correct 3515 ms 103436 KB Output is correct
43 Correct 2764 ms 117240 KB Output is correct
44 Correct 2853 ms 117072 KB Output is correct
45 Correct 2166 ms 89676 KB Output is correct
46 Correct 2211 ms 91004 KB Output is correct
47 Correct 2267 ms 119692 KB Output is correct
48 Correct 3646 ms 176604 KB Output is correct
49 Correct 2063 ms 115760 KB Output is correct
50 Correct 2044 ms 115816 KB Output is correct
51 Correct 2087 ms 115904 KB Output is correct
52 Correct 2001 ms 116228 KB Output is correct
53 Correct 1981 ms 116280 KB Output is correct
54 Correct 1941 ms 116164 KB Output is correct