oj.uz

Submission #1045185

# Submission time Handle Problem Language Result Execution time Memory
1045185 2024-08-05T18:15:31 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 132680 KB 
/* 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 = 3e5+10, K = 52, MX = 30;


struct Node{
  int X, sum = 0, sum2 = 0;
  short 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){
  auto a = split(v, it->X);
  return merge(merge(a.first, it), a.second);
}

void dfs(Nodep t){
  if(t->L) dfs(t->L);
  if(t->R) dfs(t->R);
  free(t);
}
 

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){
  Nodep A = new Node(t1, 1);
  Nodep B = new Node(t2, -1);
  T[k] = insert(T[k], A);
  T[k] = insert(T[k], B);
  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;
  }
  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(int l = 1; l <= n + 1; ++l){
    while(p < R.size() && R[p][0] == l){
      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];
      ans[idx] = get(1, n + 1, r, 1, tm);
    }
    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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2054 ms 60488 KB Output is correct
2 Correct 2476 ms 60544 KB Output is correct
3 Correct 3654 ms 61300 KB Output is correct
4 Execution timed out 5069 ms 102756 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11100 KB Output is correct
2 Correct 7 ms 11100 KB Output is correct
3 Correct 4 ms 11096 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Execution timed out 5053 ms 132680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 6 ms 11100 KB Output is correct
4 Correct 9 ms 11252 KB Output is correct
5 Correct 1476 ms 66260 KB Output is correct
6 Correct 3845 ms 89800 KB Output is correct
7 Execution timed out 5037 ms 107284 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 2054 ms 60488 KB Output is correct
9 Correct 2476 ms 60544 KB Output is correct
10 Correct 3654 ms 61300 KB Output is correct
11 Execution timed out 5069 ms 102756 KB Time limit exceeded
12 Halted 0 ms 0 KB -