제출 #552041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552041		cig32	가로등 (APIO19_street_lamps)	C++17	20 / 100	5069 ms	176948 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
#define ll __int128
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;
}
ll read() { int x; cin >> x; return (ll)x; }
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;
void insert_segment(int x, int y) {
  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) { 
  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 cmp1(query a, query b) {
  return a.x < b.x;
}
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;
}
void moshang_huakai(int array_id, int lb, int rb) {
  /*
  if(array_id == 0) {
    for(int i=0; i<=rb; i++) {
      cout << ended[i].v << " ";
      for(int j=i+1; j<=rb; j++) {
        if(ended[i].x <= ended[j].x && ended[i].y <= ended[j].y) {
          ended[j].ans += ended[i].v;
        }
      }
    }
    cout << "\n";
  }
  else if(array_id == 1) {
    for(int i=0; i<=rb; i++) {
      for(int j=i+1; j<=rb; j++) {
        if(cnt[i].x <= cnt[j].x && cnt[i].y <= cnt[j].y) {
          cnt[j].ans += cnt[i].v;
        }
      }
    }
  }
  else {
    for(int i=0; i<=rb; i++) {
      for(int j=i+1; j<=rb; j++) {
        if(sum[i].x <= sum[j].x && sum[i].y <= sum[j].y) {
          sum[j].ans += sum[i].v;
        }
      }
    }
  }
  return;
  */
  
  if(lb == rb) return;
  int mid = (lb + rb) >> 1;
  moshang_huakai(array_id, lb, mid);
  moshang_huakai(array_id, mid + 1, rb);
  if(array_id == 0) {
    sort(ended.begin() + lb, ended.begin() + mid + 1, cmp1);
    sort(ended.begin() + mid + 1, ended.begin() + rb + 1, cmp1);
  }
  else if(array_id == 1) {
    sort(cnt.begin() + lb, cnt.begin() + mid + 1, cmp1);
    sort(cnt.begin() + mid + 1, cnt.begin() + rb + 1, cmp1);
  }
  else {
    sort(sum.begin() + lb, sum.begin() + mid + 1, cmp1);
    sort(sum.begin() + mid + 1, sum.begin() + rb + 1, cmp1);
  }
  int nxt = lb;
  vector<int> upd;
  for(int i=mid+1; i<=rb; i++) {
    if(nxt <= mid) {
      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(nxt <= mid && 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.push_back(yval + 1);
        nxt++;
        if(nxt <= mid) {
          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 x: upd) {
    int qwq = bit_sum(x) - bit_sum(x - 1);
    add(x, -qwq);
  }
  if(array_id == 0) {
    sort(ended.begin() + lb, ended.begin() + mid + 1, cmp2);
    sort(ended.begin() + mid + 1, ended.begin() + rb + 1, cmp2);
  }
  else if(array_id == 1) {
    sort(cnt.begin() + lb, cnt.begin() + mid + 1, cmp2);
    sort(cnt.begin() + mid + 1, cnt.begin() + rb + 1, cmp2);
  }
  else {
    sort(sum.begin() + lb, sum.begin() + mid + 1, cmp2);
    sort(sum.begin() + mid + 1, sum.begin() + rb + 1, cmp2);
  }
}
void solve(int tc) {
  t = 0;
  cin >> n >> q;
  for(int i=1; i<=n; i++) 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;
    cin >> str;
    if(str == "toggle") {
      int i;
      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;
      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();
  /*
  cout << sz << '\n';
  cout << "Ended\n";
  for(int i=0; i<ended.size(); i++) {
    cout << ended[i].x << ' ' << ended[i].y << ' ' << ended[i].v << ' ' << ended[i].is_qry << ' ' << ended[i].id << ' ' << ended[i].ans << '\n';
  }
  cout << "Cnt\n";
  for(int i=0; i<cnt.size(); i++) {
    cout << cnt[i].x << ' ' << cnt[i].y << ' ' << cnt[i].v << '\n';
  }
  cout << "Sum\n";
  for(int i=0; i<sum.size(); i++) {
    cout << sum[i].x << ' ' << sum[i].y << ' ' << sum[i].v << '\n';
  }
  */
  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:137:19: warning: variable 'cury' set but not used [-Wunused-but-set-variable]
  137 |         int yval, cury, ysum;
      |                   ^~~~
street_lamps.cpp: In function 'void solve(int)':
street_lamps.cpp:246:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |   for(int i=0; i<ended.size(); i++) {
      |                ~^~~~~~~~~~~~~
street_lamps.cpp:251:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |   for(int i=0; i<cnt.size(); i++) {
      |                ~^~~~~~~~~~~
street_lamps.cpp:256:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |   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