Submission #1045319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045319		mychecksedad	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5097 ms	100424 KiB

street_lamps

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
#pragma GCC target("popcnt,abm,mmx,avx,avx2,lzcnt,bmi,bmi2,fma,sse,sse2,sse3,sse4,sse4.1,sse4.2,tune=native")
#pragma GCC optimize("-fipa-sra,-fgcse-lm,-fgcse,inline,unroll-all-loops,no-stack-protector,O3,fast-math,Ofast")
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 = 3e5+10, K = 52, MX = 30;


struct Node{
  int X, sum = 0, sum2 = 0;
  int Y, val;
  Node *L, *R;
  Node(){}
  Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
};
typedef Node* Nodep; 
 
void upd_sz(Nodep v){
  if(v){
    v->sum = v->val * v->X;
    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;
  }
}

 
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){
  if(!v) return it;
  if(v->Y > it->Y){
    if(v->X <= it->X) v->R = insert(v->R, it);
    else v->L = insert(v->L, it);
    upd_sz(v);
    return v;
  }else{
    auto a = split(v, it->X);
    it->L = a.ff;
    it->R = a.ss;
    upd_sz(it);
  }
  return it;
}

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

int n, q, ans[M];
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){
  if(!(l == 1 && r == n + 1)){
    Nodep A = new Node(t1, 1);
    Nodep B = new Node(t2, -1);
    T[k] = insert(T[k], A);
    T[k] = insert(T[k], B);
  }
  // dfs2(T[k]);en;en;
   // cout << "insert:" << l << ' ' << r << ' ' << p << ' ' << t1 << ' ' << t2 << '\n';

  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;
    T[k] = merge(halves.ff, halves.ss);

    return val;
  }
  // dfs2(T[k]);en;en;
  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;
    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);
}

void F(int l, int r, int p, int k){
  if(l == r){
    dfs(T[k]);
    return;
  }
  int m = l+r>>1;
  if(p <= m) F(l, m, p, k<<1);
  else F(m+1, r, p, k<<1|1);
  if(p == r) dfs(T[k]);
}

vector<array<int, 3>> Q[M];
void solve(){
  // cout << sizeof(Node) << '\n';
  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 p: S){
    R.pb({p[0], p[1], p[2], q});
  }
  S.clear();

  sort(all(R));
  build(1, n + 1, 1);
  int p = 0;

  // for(auto f: R){
  //   cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
  // }
  // en;en;

  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;
    }
    F(1, n+1, l, 1);
  }



  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:20:13: warning: 'Node::R' will be initialized after [-Wreorder]
   20 |   Node *L, *R;
      |             ^
street_lamps.cpp:19:10: warning:   'int Node::val' [-Wreorder]
   19 |   int Y, val;
      |          ^~~
street_lamps.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp:19:10: warning: 'Node::val' will be initialized after [-Wreorder]
   19 |   int Y, val;
      |          ^~~
street_lamps.cpp:18:10: warning:   'int Node::sum' [-Wreorder]
   18 |   int X, sum = 0, sum2 = 0;
      |          ^~~
street_lamps.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |   ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:114:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:133:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:148:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:165:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |   int m = l+r>>1;
      |           ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:240: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]
  240 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:266:15: warning: unused variable 'aa' [-Wunused-variable]
  266 |   int tt = 1, aa;
      |               ^~

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