제출 #552048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552048		cig32	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5050 ms	190052 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 s[MAXN]; int n, q, t;
struct query {
  int x, y, v;
  bool is_qry;
  int ans;
  int id;
};
vector<query> ended, cnt, sum;
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;
int ct1 = 0, ct2 = 0;
void insert_segment(int x, int y) {
  ++ct1;
  l[y] = x;
  r[x] = y;
  all_segments.insert({y, x});
  cnt.push_back({x, y, 1, 0, 0, ++global_id});
  sum.push_back({x, y, t, 0, 0, ++global_id});
  simple_cnt[x][y] += 1;
  simple_sum[x][y] += t;
}
void delete_segment(int x, int y) { 
  ++ct2;
  all_segments.erase({y, x});
  simple_ended[x][y] += t - simple_sum[x][y];
  ended.push_back({x, y, t - simple_sum[x][y], 0, 0, ++global_id});
  cnt.push_back({x, y, -simple_cnt[x][y], 0, 0, ++global_id});
  simple_cnt[x].erase(y);
  sum.push_back({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 s = 0;
  for(;x;x-=x&-x) s += bit[x];
  return s;
}
int ct3 = 0;
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);
  vector<pair<int, int> > ll, rr;
  for(int i=lb; i<=mid; i++) {
    if(array_id == 0) ll.push_back({ended[i].x, i});
    else if(array_id == 1) ll.push_back({cnt[i].x, i});
    else ll.push_back({sum[i].x, i});
  }
  for(int i=mid+1; i<=rb; i++) {
    if(array_id == 0) rr.push_back({ended[i].x, i});
    else if(array_id == 1) rr.push_back({cnt[i].x, i});
    else rr.push_back({sum[i].x, i});
  }
  sort(ll.begin(), ll.end());
  sort(rr.begin(), rr.end());
  int nxt = ll[0].second;
  int ti = 0;
  int upd[rb - mid + 5];
  int newidx = 0;
  for(int j=mid+1; j<=rb; j++) {
    int i = rr[j - (mid + 1)].second;
    if(ti < ll.size()) {
      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 < ll.size() && 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);
        //cout << "hi " << yval << " += " << ysum << ", " << array_id << "\n";
        upd[newidx++] = yval + 1;
        ti++;
        if(ti >= ll.size()) 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];
    int qwq = bit_sum(x) - bit_sum(x - 1);
    add(x, -qwq);
  }
  
  
}
void solve(int tc) {
  t = 0;
  //n = 300000, q = 300000;
  cin >> n >> q;
  for(int i=1; i<=n; i++) {
    //s[i] = char(rnd(0, 1) + '0'); 
    cin >> s[i];
  }
  for(int i=0; i<=n+1; i++) l[i] = r[i] = -1;
  for(int i=1; i<=n; i++) {
    if(s[i] == '1') {
      int j = i;
      while(j + 1 <= n && s[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;
      s[i] = (s[i] == '1' ? '0' : '1');
      if(s[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.push_back({a, n, 0, 1, 0, ++global_id});
      ended.push_back({a, b - 1, 0, 1, 0, ++global_id});
      cnt.push_back({a, n, 0, 1, 0, ++global_id});
      cnt.push_back({a, b - 1, 0, 1, 0, ++global_id});
      sum.push_back({a, n, 0, 1, 0, ++global_id});
      sum.push_back({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, ended.size() - 1);
  moshang_huakai(1, 0, cnt.size() - 1);
  moshang_huakai(2, 0, sum.size() - 1);
  vector<int> ended_ans, cnt_ans, sum_ans;
  for(int i=0; i<ended.size(); i++) {
    if(ended[i].is_qry == 1) {
      ended_ans.push_back(ended[i].ans);
    }
  }
  for(int i=0; i<cnt.size(); i++) {
    if(cnt[i].is_qry == 1) {
      cnt_ans.push_back(cnt[i].ans);
    }
  }
  for(int i=0; i<sum.size(); 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.

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'void moshang_huakai(int, int, int)':
street_lamps.cpp:102:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(ti < ll.size()) {
      |        ~~~^~~~~~~~~~~
street_lamps.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |       while(ti < ll.size() && xval <= curx) {
      |             ~~~^~~~~~~~~~~
street_lamps.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         if(ti >= ll.size()) break;
      |            ~~~^~~~~~~~~~~~
street_lamps.cpp:108:19: warning: variable 'cury' set but not used [-Wunused-but-set-variable]
  108 |         int yval, cury, ysum;
      |                   ^~~~
street_lamps.cpp: In function 'void solve(int)':
street_lamps.cpp:221:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |   for(int i=0; i<ended.size(); i++) {
      |                ~^~~~~~~~~~~~~
street_lamps.cpp:226:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |   for(int i=0; i<cnt.size(); i++) {
      |                ~^~~~~~~~~~~
street_lamps.cpp:231:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |   for(int i=0; i<sum.size(); i++) {
      |                ~^~~~~~~~~~~

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