Submission #1161859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161859		mychecksedad	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2150 ms	90968 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 = 1e5+10, K = 52, MX = 30;

struct Fenwick{
  int n;
  ll tot = 0;
  vector<int> t;
  vector<int> q;
  void init(int _n){
    n = _n;
    t.resize(n+1, 0);
  }
  void reset(){
    for(int x: q) t[x] = 0;
    q.clear();
    tot = 0;
  }
  void add(int v, int x){
    tot += x;
    ++v;
    while(v <= n){
      t[v]+=x;
      v += (v&-v);
    }
  }
  int get(int v){
    int res = 0;
    assert(v < t.size());
    ++v;
    while(v > 0){
      res += t[v];
      v -= (v&-v);
    }
    return res;
  }
};
 
int n, q, ans[N];
Fenwick fw;
vector<array<int, 4>> Q, T;
vector<array<int, 4>> events, queries;
void f(int l, int r){
  if(l == r) return;
  int m = l+r>>1;
  f(l, m);
  f(m + 1, r);

  for(int i = l; i <= m; ++i){
    auto [x, y, t1, t2] = T[i];
    if(y > 0){
      --y;
      // cout << y << ' ' << t1 << endl;
      // cout << x << ' ' << y << ' ' << t1 << ' ' << t2 << ' ' << l << ' ' << r << '\n';
      events.pb({y, y, t1, t2});
      events.pb({t1 + 1, y, t1, -t2});
      // events.pb({t1 + 1, });
    }
  }
  for(int i = m + 1; i <= r; ++i){
    auto [x, y, t1, t2] = T[i];
    if(y < 0){
      y = -y; 
      --y;
      queries.pb({y, t1, t2, 31});
    }
  }
  sort(all(events));
  sort(all(queries));
  int ptr = 0;
  for(auto [L, R, idx, sus]: queries){
    while(ptr < events.size() && events[ptr][0] <= L){
      fw.add(events[ptr][1], events[ptr][3]);
      fw.add(events[ptr][2] + 1, -events[ptr][3]);
      ++ptr;
    }
    ans[idx] += fw.get(R);
  }

  for(int i = 0; i < ptr; ++i){
    auto [x,y,z,t] = events[i];
    fw.add(y, -t);
    fw.add(z+1, t);
  }

  events.clear();
  queries.clear();
}


string s;
void solve(){
  cin >> n >> q >> s;
  set<array<int, 3>> S;
  fw.init(n+1);
  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;
      auto it = S.upper_bound({x, MOD, MOD});
      if(it != S.begin()){
        if((*prev(it))[1] >= y && (*prev(it))[0] <= x){
          ans[qt] += i;
        }
      }
      Q.pb({x, y, i, qt++});
    }

  // for(auto [x,y ,z, t] : T) cout << x << ' ' << y << ' ' << z << ' ' << t << '\n';
  // en;
  }
  for(auto [x,y ,z] : S) T.pb({z, q + 1, x, y});

  vector<array<int, 4>> TT;
  for(auto [x, y, t1, t2]: T){
    swap(x, t1);
    swap(y, t2);
    TT.pb({t1, x+1, y, -t1});
    TT.pb({t2+1, x+1, y, t2+1});
    // cout << x << ' ' << y << ' ' << t1 << '\n';
    // cout << x << ' ' << y << ' ' << t2 << '\n';
  }
  T.clear();
  for(auto [x, y, idx, qt]: Q){
    TT.pb({idx, -(x+1), y, qt});
  }
  Q.clear();
  sort(all(TT));
  T.swap(TT);

  fw.init(n + 37);
  f(0, int(T.size())-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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20