Submission #1045161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045161		mychecksedad	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	3901 ms	524288 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
const int N = 2e6+100, M = 1e5+10, K = 52, MX = 30;


struct Node{
  int X, Y, sz = 0, val = 0, sum = 0, sum2 = 0;
  Node *L, *R;
  Node(){}
  Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), sz(key), val(val), sum(key * val), sum2(val) {}
  // Node(int key, int pr) : X(key), Y(pr), L(nullptr), R(nullptr) {}
};
typedef Node* Nodep; 
 
void upd_sz(Nodep v){
  if(v){
    v->sz = v->X;
    if(v->L) v->sz = min(v->L->sz, v->sz);
    if(v->R) v->sz = min(v->R->sz, v->sz);

    v->sum = v->val * v->X;//cout << "ff ";
    // cout << v->X << ' ' << v->sum << ' ' << v->val << "\n";
    v->sum2 = v->val;
    if(v->L) v->sum += v->L->sum;
    if(v->R) v->sum += v->R->sum;

    if(v->L) v->sum2 += v->L->sum2;
    if(v->R) v->sum2 += v->R->sum2;
    // cout << "ff :";
    // cout << v->sum << ' ' << v->val << ' ' << v->X << ' ' << v->sum2 << '\n';
  }
}

int get(Nodep x){
  if(!x) return MOD;
  return x->sz;
}
 
pair<Nodep, Nodep> split(Nodep v, int key){
  if(!v){
    return {v, v};
  }
  else if(v->X <= key){
    auto p = split(v->R, key);
    v->R = p.first;
    upd_sz(v);
    return {v, p.second};
  }else{
    auto p = split(v->L, key);
    v->L = p.second;
    upd_sz(v);
    return {p.first, v};
  }
}
 
Nodep merge(Nodep l, Nodep r){
  if(!l || !r){
    return l ? l : r;
  }else if(l->Y > r->Y){
    auto p = merge(l->R, r);
    l->R = p;
    upd_sz(l);
    return l;
  }else{
    auto p = merge(l, r->L);
    r->L = p;
    upd_sz(r);
    return r;
  }
}
Nodep insert(Nodep v, Nodep it){
  auto a = split(v, it->X);
  return merge(merge(a.first, it), a.second);
}

void dfs(Nodep t){
  if(t->L)
  cout << "go left: ";
  if(t->L) dfs(t->L);
  cout << "par: ";
  cout << t->X << ' ';
  if(t->R)
  cout << "go right: ";
  if(t->R) dfs(t->R);
}
 

int n, q, ans[N];
string s;
Nodep T[N];

void build(int l, int r, int k){
  if(l == r){
    T[k] = new Node(0, 0);
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = new Node(0, 0);
}

void upd(int l, int r, int p, int k, int t1, int t2){
  Nodep A = new Node(t1, 1);
  Nodep B = new Node(t2, -1);
  T[k] = insert(T[k], A);
  // if(l == r && l == 4){
  //   cout << "dfs : ";
  //   dfs(T[k]);
  //   en;en;en;
  // }
  T[k] = insert(T[k], B);
  // cout << "insert:" << l << ' ' << r << ' ' << p << ' ' << t1 << ' ' << t2 << '\n';
  // if(l == r && l == 4){
  //   cout << "dfs : ";
  //   dfs(T[k]);
  //   en;en;en;
  // }
  if(l == r){
    return;
  }
  int m = l+r>>1;
  if(p <= m) upd(l, m, p, k<<1, t1, t2);
  else upd(m+1, r, p, k<<1|1, t1, t2);
}

int get(int l, int r, int p, int k, ll tm){
  if(l == r){
    int val = 0;
    auto halves = split(T[k], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
    // dfs(halves.ff); cout << " dfs" << '\n';
    // cout << halves.ff->szz << ' ' << halves.ff->X << ' ' << halves.ff->val << ' ' << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';
    
    T[k] = merge(halves.ff, halves.ss);
    return val;
  }
  int m = l+r>>1;
  if(p <= m){
    int val = 0;
    auto halves = split(T[k<<1|1], tm);
    val += halves.ff->sum2 * tm - halves.ff->sum;
    // cout << halves.ff->X << ' ' << tm << ' ' << l << ' ' << r << ' ' << halves.ff->sum2 << ' ' << halves.ff->sum << ' ' << val << '\n';
    
    T[k<<1|1] = merge(halves.ff, halves.ss);
    
    return get(l, m, p, k<<1, tm) + val;
  }
  return get(m+1, r, p, k<<1|1, tm);
}

vector<array<int, 3>> Q[N];
void solve(){
  cin >> n >> q >> s;

  vector<array<int, 4>> R;
  int last = 1;
  s += '0';
  set<array<int, 3>> S;
  for(int i = 0; i <= n; ++i){
    if(s[i] == '0'){
      S.insert({last, i + 1, 0});
      last = i + 2;
    }
  }

  int qq = 0;

  for(int i = 0; i < q; ++i){
    string x; int a, b; cin >> x;
    if(x == "toggle"){
      cin >> a;
      --a;
      if(s[a] == '0'){
        s[a] = '1';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        auto it2 = prev(it);
        auto x = *it, y = *it2;
        S.erase(it2);
        S.erase(S.find(x));
        S.insert({y[0], x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
        R.pb({y[0], y[1], y[2], i + 1});
      }else{
        s[a] = '0';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto x = *it;
        S.erase(it);
        S.insert({x[0], a, i + 1}); // check
        S.insert({a + 1, x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
      }
    }else{
      cin >> a >> b;
      Q[a].pb({b, i + 1, qq});
      qq++;
    }
    // for(auto f: S){
    //   cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';
    // }
    // en;
    // cout << endl;
  }

  for(auto p: S){
    R.pb({p[0], p[1], p[2], q});
  }

  sort(all(R));
  // for(auto f: R){
  //   cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
  // }
  // en;en;
  build(1, n + 1, 1);
  int p = 0;
  for(int l = 1; l <= n + 1; ++l){
    while(p < R.size() && R[p][0] == l){
      // cout << R[p][0] << ' ' << R[p][1] << ' ' << R[p][2] << ' ' << R[p][3] << '\n';
      int r = R[p][1], t1 = R[p][2], t2 = R[p][3];
      upd(1, n+1, r, 1, t1, t2);
      ++p;
    }
    for(auto query: Q[l]){
      int r = query[0], tm = query[1], idx = query[2];
      // cout << l << ' ' << r << '\n';
      ans[idx] = get(1, n + 1, r, 1, tm);
      // cout << ans[idx] << ' ';
      // en;en;
    }
  }



  for(int i = 0; i < qq; ++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;
} 

Compilation message (stderr)

street_lamps.cpp: In constructor 'Node::Node(int, int)':
street_lamps.cpp:17:13: warning: 'Node::R' will be initialized after [-Wreorder]
   17 |   Node *L, *R;
      |             ^
street_lamps.cpp:16:13: warning:   'int Node::sz' [-Wreorder]
   16 |   int X, Y, sz = 0, val = 0, sum = 0, sum2 = 0;
      |             ^~
street_lamps.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), sz(key), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:106:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:131:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:147:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:231:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:254:15: warning: unused variable 'aa' [-Wunused-variable]
  254 |   int tt = 1, aa;
      |               ^~

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