Submission #1143915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143915		mychecksedad	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	1135 ms	415112 KiB

street_lamps

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e7+10, K = 52, MX = 30;

struct Node{
  Node *L, *R;
  int hi, lo, lazy_left=0, lazy_right=0, val = 0;
  Node(){}
  Node(int l, int r){
    lo = l, hi = r;
    L=R=nullptr;
    lazy_right=0;
    lazy_left=0;
  }
  void extendL(){
    if(!L) L = new Node(lo, hi+lo>>1);
  }
  void extendR(){
    if(!R) R = new Node((hi+lo>>1)+1, hi);
  }
  void pushL(){
    if(L){
      L->lazy_left += lazy_left;
      L->lazy_right += lazy_left;
      L->val += lazy_left * (L->hi-L->lo+1);
      lazy_left = 0;
    }
  }
  void pushR(){
    if(R){
      R->lazy_left += lazy_right;
      R->lazy_right += lazy_right;
      R->val += lazy_right * (R->hi-R->lo+1);
      lazy_right = 0;
    }
  }
  void add(int l, int r){
    if(lo > r || l > hi ) return;
    if(l <= lo && hi <= r){
      val += hi-lo+1;
      lazy_left++;
      lazy_right++;
      return;
    }
    int m = lo+hi>>1;
    // if(l <= m){
      extendL();
      pushL();
      L->add(l, r);
    // }
    // if(r >= m+1){
      extendR();
      pushR();
      R->add(l, r);
    // }
    val = (L?L->val:lazy_left*((hi+lo>>1) - lo + 1)) + (R?R->val:lazy_right*(hi - (hi+lo>>1)));
  }
  int get(int p){
    if(lo == hi){
      return val;
    }
    int m = lo+hi>>1;
    if(p <= m){
      extendL();
      pushL();
      return L->get(p);
    }
    extendR();
    pushR();
    return R->get(p) + (L?L->val:lazy_left*((lo+hi>>1) - lo + 1));// + (R?R->val:0);
  }

};
typedef Node* Nodep;
struct SegTree{
  Nodep root = nullptr;
  SegTree(){}
  SegTree(int l, int r){
    root = new Node(l, r);
  }
  void add(int t1, int t2){
    root->add(t1, t2);
  }
  int get(int l){
    return root->get(l);
  }
};
 
int n, q, ans[N];
SegTree *TT[N];
void add(int pos, int t1, int t2){
  int v = pos;
  while(v <= n+1){
    TT[v]->add(t1, t2);
    v += v&-v;
  }
}
int get(int tm, int y){
  int v = tm-1;
  int ans = 0;
  while(v > 0){
    ans -= TT[v]->get(y);
    v -= v&-v;
  }
  v = n+1;
  while(v > 0){
    ans += TT[v]->get(y);
    v -= v&-v;
  }
  // cout << tm << ' ' << y << ' ' << mx << ' ' << ans << '\n';
  return ans;
}

string s;
vector<array<int, 4>> Q, T;
void solve(){
  cin >> n >> q >> s;
  set<array<int, 3>> S;
  int L = 1;
  s += '0';
  for(int j = 0; j < n + 1; ++j){
    if(s[j] == '0'){
      S.insert({L, j + 1, 0});
      L = j + 2;
    }
  }
  // for(auto [x, y, z]: S) cout << x << ' ' << y << ' ' << z << '\n';
  int qt = 0;
  for(int i = 1; i <= q; ++i){
    string t; cin >> t;
    if(t == "toggle"){
      int x; cin >> x;
      --x;
      if(s[x] == '0'){
        s[x] = '1';
        x++;
        auto it = S.lower_bound(array<int, 3> {x + 1, -1, -1});
        T.pb({(*it)[2], i-1, (*it)[0], (*it)[1]});
        auto v = *it;
        assert(it != S.end());
        S.erase(it);
        it = S.lower_bound(array<int, 3> {x + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto u = *it;
        S.erase(it);
        T.pb({u[2], i-1, u[0], u[1]});
        S.insert({u[0], v[1], i});
      }else{
        s[x] = '0';
        ++x;
        auto it = S.lower_bound(array<int, 3> {x + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto v = *it;
        T.pb({v[2], i-1, v[0], v[1]});
        S.erase(it);
        S.insert({v[0], x, i});
        S.insert({x + 1, v[1], i});
      }
    }else{
      int x, y;
      cin >> x >> y;
      Q.pb({x, y, i, qt++});
    }
    // for(auto [x,y,z]: S) cout << x << ' ' << y << ' ' << z << '\n';
    //   en;
  }
  for(auto [x,y ,z] : S) T.pb({z, q + 1, x, y});
  for(int i = 0; i < T.size(); ++i) swap(T[i][0], T[i][2]), swap(T[i][1], T[i][3]);
  
  // cout << "T:\n";
  //   for(auto [x, y,z,t]: T) cout << x << ' ' << y << ' ' << z << ' ' << t << '\n';

  sort(all(T));
  sort(all(Q));
  int pt = 0;
  for(int i = 1; i <= n + 2; ++i){
    TT[i] = new SegTree(0, q + 2);
  }
  for(int j = 0; j < qt; ++j){
    while(pt < T.size() && T[pt][0] <= Q[j][0]){
      int i = pt;
      add(T[i][1], T[i][2], T[i][3]);
      // cout << "T: ";
      // if(T[pt][1] >= Q[j][1] && T[pt][1] <= Q[j][2]) cout << "d";
      // cout << T[i][0] << ' ' << T[i][1] << ' ' << T[i][2] << ' ' << T[i][3] << '\n';
      ++pt;
    } 
    // cout << Q[j][2] << ' ' << Q[j][0] << ' ' << Q[j][1] << "f\n";
    ans[Q[j][3]] = get(Q[j][1], Q[j][2]-1);
  }


  for(int i = 0; i < qt; ++i) cout << ans[i] << '\n';
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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