oj.uz

Submission #498659

# Submission time Handle Problem Language Result Execution time Memory
498659 2021-12-26T04:45:11 Z model_code Weirdtree (RMI21_weirdtree) C++17
100 / 100
 602 ms 41140 KB 
// weirdtree_100_george.cpp

#include <bits/stdc++.h>
#include "weirdtree.h"

using namespace std;

class SegmentTree{
public:
  struct node_t{
    int max1;
    int max2;
    int cntMax;
    long long sum;
    int lazy;

    node_t(){
      this->max1 = 0;
      this->max2 = 0;
      this->cntMax = 0;
      this->sum = 0;
      this->lazy = 0;
    }

    node_t(int val){
      this->max1 = val;
      this->max2 = 0;
      this->cntMax = 1;
      this->sum = val;
      this->lazy = 0;
    }

    node_t operator + (const node_t &other)const{
      node_t ans;

      ans.sum = (this->sum + other.sum);
      ans.lazy = 0;
    
      if(this->max1 == other.max1){
        ans.max1 = this->max1;
        ans.cntMax = this->cntMax + other.cntMax;
        ans.max2 = max(this->max2,other.max2);
      }else if(this->max1 > other.max1){
        ans.max1 = this->max1;
        ans.cntMax = this->cntMax;
        ans.max2 = max(this->max2,other.max1);
      }else{
        ans.max1 = other.max1;
        ans.cntMax = other.cntMax;
        ans.max2 = max(this->max1,other.max2);
      }
    
      return ans;
    }

    void propagate(int lazy){
      this->max1 -= lazy;
      this->sum -= 1LL * lazy * this->cntMax;
      this->lazy += lazy;
    }

  };

private:
  int n;
  vector<node_t> aint;

  void build(int nod,int st,int dr,int v[]){
    if(st == dr){
      aint[nod] = node_t(v[st]);
      return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid,v);
    build(nod * 2 + 1,mid + 1,dr,v);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  void propagate(int nod,int st,int dr){
    if(aint[nod].lazy == 0 || st == dr){
      return ;
    }
    int tmpMax = max(aint[nod * 2].max1,aint[nod * 2 + 1].max1);
    if(aint[nod * 2].max1 == tmpMax){
      aint[nod * 2].propagate(aint[nod].lazy);
    }
    if(aint[nod * 2 + 1].max1 == tmpMax){
      aint[nod * 2 + 1].propagate(aint[nod].lazy);
    }

    aint[nod].lazy = 0;
  }
  

  void updateSet(int nod,int st,int dr,int pos,int value){
    propagate(nod,st,dr);

    if(dr < pos || st > pos){
      return ;
    }
    if(st == dr){
      aint[nod] = node_t(value);
      return ;
    }

    int mid = (st + dr) / 2;

    updateSet(nod * 2,st,mid,pos,value);
    updateSet(nod * 2 + 1,mid + 1,dr,pos,value);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  void updateSubtract(int nod,int st,int dr,int l,int r,int value,int &bonus,int maxValue){
    propagate(nod,st,dr);
    if(value + (bonus > 0) == 0 || dr < l || st > r || (l <= st && dr <= r && aint[nod].max1 != maxValue)){
      return ;
    }
    if(l <= st && dr <= r && (bonus == 0 || bonus >= dr - st + 1) && (aint[nod].max2 == 0 || aint[nod].max1 - value - (bonus > 0) > aint[nod].max2)){
      aint[nod].propagate(value + (bonus > 0));
      bonus -= (bonus > 0) * aint[nod].cntMax;
      return ;
    }
    int mid = (st + dr) / 2;
 
    updateSubtract(nod * 2,st,mid,l,r,value,bonus,maxValue);
    updateSubtract(nod * 2 + 1,mid + 1,dr,l,r,value,bonus,maxValue);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
  }

  node_t query(int nod,int st,int dr,int l,int r){
    propagate(nod,st,dr);
    if(dr < l || st > r){
      return node_t();
    }

    if(l <= st && dr <= r){
      return aint[nod];
    }

    int mid = (st + dr) / 2;

    return query(nod * 2,st,mid,l,r) + query(nod * 2 + 1,mid + 1,dr,l,r);
  }
  

public:

  SegmentTree(){
    ;
  }

  SegmentTree(int n,int v[]){
    this->n = n;
    this->aint = vector<node_t>(4 * n + 5, node_t());
    build(1,1,n,v);
  }
  
  node_t query(int st,int dr){
    return this->query(1,1,n,st,dr);
  }

  void updateSet(int pos,int value){
    this->updateSet(1,1,n,pos,value);
  }

  void updateSubtract(int l,int r,int k,int bonus,int maxValue){
    this->updateSubtract(1,1,n,l,r,k,bonus,maxValue);
  }
};

SegmentTree aint;

void initialise(int n,int q,int v[]){
  aint = SegmentTree(n, v);
}

void cut(int l,int r,int k){
  while(k > 0){
    SegmentTree::node_t tmp = aint.query(l,r);
    if(tmp.max1 == 0){
      break;
    }
    if((tmp.max1 - tmp.max2) <= k / tmp.cntMax){
      k -= (tmp.max1 - tmp.max2) * tmp.cntMax;
      aint.updateSubtract(l,r,tmp.max1 - tmp.max2,0,tmp.max1);
    }else{
      int divResult = k / tmp.cntMax;
      aint.updateSubtract(l,r,divResult,k - divResult * tmp.cntMax,tmp.max1);
      k = 0;
    }
  }
}

void magic(int i,int x){
  aint.updateSet(i,x);
}

long long inspect(int l,int r){
  return aint.query(l,r).sum;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 94 ms 10656 KB Output is correct
4 Correct 101 ms 10488 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 602 ms 40372 KB Output is correct
4 Correct 493 ms 41140 KB Output is correct
5 Correct 516 ms 39668 KB Output is correct
6 Correct 473 ms 39128 KB Output is correct
7 Correct 12 ms 10640 KB Output is correct
8 Correct 47 ms 10700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10640 KB Output is correct
2 Correct 47 ms 10700 KB Output is correct
3 Correct 148 ms 38056 KB Output is correct
4 Correct 152 ms 39772 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 94 ms 10656 KB Output is correct
4 Correct 101 ms 10488 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 12 ms 10640 KB Output is correct
8 Correct 47 ms 10700 KB Output is correct
9 Correct 108 ms 10688 KB Output is correct
10 Correct 85 ms 10352 KB Output is correct
11 Correct 76 ms 10288 KB Output is correct
12 Correct 102 ms 10880 KB Output is correct
13 Correct 89 ms 10984 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 94 ms 10656 KB Output is correct
4 Correct 101 ms 10488 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 602 ms 40372 KB Output is correct
8 Correct 493 ms 41140 KB Output is correct
9 Correct 516 ms 39668 KB Output is correct
10 Correct 473 ms 39128 KB Output is correct
11 Correct 148 ms 38056 KB Output is correct
12 Correct 152 ms 39772 KB Output is correct
13 Correct 108 ms 10688 KB Output is correct
14 Correct 85 ms 10352 KB Output is correct
15 Correct 76 ms 10288 KB Output is correct
16 Correct 102 ms 10880 KB Output is correct
17 Correct 89 ms 10984 KB Output is correct
18 Correct 12 ms 10640 KB Output is correct
19 Correct 47 ms 10700 KB Output is correct
20 Correct 415 ms 37272 KB Output is correct
21 Correct 400 ms 40128 KB Output is correct
22 Correct 432 ms 39544 KB Output is correct
23 Correct 413 ms 39500 KB Output is correct
24 Correct 462 ms 38612 KB Output is correct