Submission #699278

#	Time	Username	Problem	Language	Result	Execution time	Memory
699278		Abrar_Al_Samit	가로등 (APIO19_street_lamps)	C++17	0 / 100	3 ms	3916 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;

const int nax = 3e5 + 2;
const int qax = 3e5 + 2;
const int INF = 1e9;

struct BIT {
  vector<int>fen;
  int N;
  BIT(int sz) {
    fen.assign(sz+10, 0);
    N = sz;
  }

  void add(int pos, int val) {
    assert(pos>0);
    while(pos<=N) {
      fen[pos] += val;
      pos += (pos&-pos);
    }
  }
  int get(int pos) {
    int sum = 0;
    while(pos>0) {
      sum += fen[pos];
      //cerr<<pos<<' '<<sum<<endl;
      pos -= (pos&-pos);
    }
    return sum;
  }
  int get(int l, int r) {
    int sum = get(r);
    if(l>1) sum -= get(l-1);
    return sum;
  }
};
void PlayGround() {
  int n, q;
  cin>>n>>q;

  string s;
  cin>>s;
  s = '@' + s;
  int prv = 0;

  int ans[q+1];
  memset(ans, -1, sizeof ans);


  set<array<int, 3>>st; // l, r, index
  vector<array<int, 5>>bag; // l, t0, t1, r, index


  s += '0';
  for(int i=1; i<=n+1; ++i) {
    if(s[i]=='0') {
      if(prv!=i-1) {
        st.insert({prv+1, i-1, (int)bag.size()});
        bag.push_back({prv+1, 1, q, i-1, -1});
      }
      prv = i;
    }
  }
  s.pop_back();


  for(int i=1; i<=q; ++i) {
    string type;
    cin>>type;
    if(type=="toggle") {
      int j;
      cin>>j;

      if(s[j]=='0') {
        s[j] = '1';
        auto it = st.lower_bound({j, 0, 0});
        //cerr<<(*it)[0]<<' '<<(*it)[1]<<endl;
        if(it!=st.end() && (*it)[0]==j+1 && it!=st.begin() && (*prev(it))[1]==j-1) {
          auto x = prev(it), y = it;
          st.erase(x), st.erase(y);

          bag[(*x)[2]][2] = i;
          bag[(*y)[2]][2] = i;

          st.insert({(*x)[0], (*y)[1], (int)bag.size()});
          bag.push_back({(*x)[0], i+1, q, (*y)[1], -1});

        } else if(it!=st.end() && (*it)[0]==j+1) {
          auto x = it;
          st.erase(x);

          bag[(*x)[2]][2] = i;

          st.insert({j, (*x)[1], (int)bag.size()});
          bag.push_back({j, i+1, q, (*x)[1], -1});
        } else if(it!=st.begin() && (*prev(it))[1]==j-1) {
          auto x = it;
          st.erase(x);

          bag[(*x)[2]][2] = i;

          st.insert({(*x)[0], j, (int)bag.size()});
          bag.push_back({(*x)[0], i+1, q, j, -1});

        } else {
          st.insert({j, j, (int)bag.size()});
          bag.push_back({j, i+1, q, j, -1});
        }

      } else {
        s[j] = '0';

        auto it = st.lower_bound({j, 0, 0});
        if(it==st.end() || (*it)[0]!=j) it = prev(it);
        st.erase(it);
        bag[(*it)[2]][2] = i;

        if((*it)[1]==(*it)[0]) {

        } else if(j==(*it)[0]) {
          st.insert({j+1, (*it)[1], (int)bag.size()});
          bag.push_back({j+1, i+1, q, (*it)[1], -1});
        } else if(j==(*it)[1]) {
          st.insert({(*it)[0], j-1, (int)bag.size()});
          bag.push_back({(*it)[0], i+1, q, j-1, -1});
        } else {
          st.insert({(*it)[0], j-1, (int)bag.size()});
          bag.push_back({(*it)[0], i+1, q, j-1, -1});

          st.insert({j+1, (*it)[1], (int)bag.size()});
          bag.push_back({j+1, i+1, q, (*it)[1], -1});
        }
      }
    } else {
      int a, b;
      cin>>a>>b;
      --b;

      bag.push_back({a, INF, INF, b, i});
    }
  }


  BIT b1(nax), b2(qax), b3(qax);

  sort(bag.begin(), bag.end());
  // for(auto x : bag) {
  //   cerr<<x[0]<<' '<<x[1]<<' '<<x[2]<<' '<<x[3]<<' '<<x[4]<<endl;
  // }
  for(auto x : bag) {
    //cerr<<x[4]<<endl;
    if(x[4]!=-1) {
      ans[x[4]] = b1.get(x[3], nax);
      ans[x[4]] -= b2.get(x[4], qax);
      ans[x[4]] += b3.get(x[4], qax) * x[4]; 

    } else {
      b1.add(x[3], x[2]-x[1]+1);
      b2.add(x[2], x[2]);
      b3.add(x[2], 1);
    }
  } 

  for(int i=1; i<=q; ++i) if(ans[i]!=-1) {
    cout<<ans[i]<<'\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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