oj.uz

Submission #641042

# Submission time Handle Problem Language Result Execution time Memory
641042 2022-09-15T19:48:37 Z Alexandruabcde Weirdtree (RMI21_weirdtree) C++14
100 / 100
 589 ms 38788 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int NMAX = 3e5 + 5;

int Size;

struct Node {
   Node *Left, *Right;

   LL sum;
   int Max;
   int freq;
   int Second_Max;

   int lazy_set;

   Node (int value = 0) {
      Left = Right = nullptr;
      sum = value;
      Max = value;
      freq = 1;
      Second_Max = -1;
      lazy_set = -1;
   }
};

void JoinSons (Node *Tree) {
   Tree->sum = Tree->Left->sum + Tree->Right->sum;

   if (Tree->Left->Max == Tree->Right->Max) {
      Tree->Max = Tree->Left->Max;
      Tree->freq = Tree->Left->freq + Tree->Right->freq;

      Tree->Second_Max = max(Tree->Left->Second_Max, Tree->Right->Second_Max);
   }
   else if (Tree->Left->Max > Tree->Right->Max) {
      Tree->Max = Tree->Left->Max;
      Tree->freq = Tree->Left->freq;

      Tree->Second_Max = max(Tree->Left->Second_Max, Tree->Right->Max);
   }
   else {
      Tree->Max = Tree->Right->Max;
      Tree->freq = Tree->Right->freq;

      Tree->Second_Max = max(Tree->Left->Max, Tree->Right->Second_Max);
   }
}

Node JoinNodes (Node a, Node b) {
   Node ans;

   ans.lazy_set = -1;
   ans.sum = a.sum + b.sum;

   if (a.Max == b.Max) {
      ans.Max = a.Max;
      ans.freq = a.freq + b.freq;

      ans.Second_Max = max(a.Second_Max, b.Second_Max);
   }
   else if (a.Max < b.Max) {
      ans.Max = b.Max;
      ans.freq = b.freq;

      ans.Second_Max = max(a.Max, b.Second_Max);
   }
   else {
      ans.Max = a.Max;
      ans.freq = a.freq;

      ans.Second_Max = max(a.Second_Max, b.Max);
   }

   return ans;
}

void Init (Node *Tree, int a, int b) {
   if (a == b) return;

   int mij = (a + b) / 2;

   Tree->Left = new Node;
   Tree->Right = new Node;

   Init(Tree->Left, a, mij);
   Init(Tree->Right, mij+1, b);
}

void Change_Value (Node *Tree, int lazy) {
   if (Tree->Max < lazy) return;

   Tree->sum -= 1LL * Tree->Max * Tree->freq;
   Tree->Max = lazy;
   Tree->sum += 1LL * Tree->Max * Tree->freq;

   Tree->lazy_set = lazy;
}

void Propag (Node *Tree, int a, int b) {
   if (a == b) return;

   if (Tree->lazy_set == -1) return;

   Change_Value(Tree->Left, Tree->lazy_set);
   Change_Value(Tree->Right, Tree->lazy_set);

   Tree->lazy_set = -1;
}

void Set_Value (Node *Tree, int a, int b, int poz, int val) {
   Propag(Tree, a, b);
   if (a == b) {
      Tree->Max = val;
      Tree->freq = 1;

      Tree->sum = val;

      return;
   }

   int mij = (a + b) / 2;

   if (poz <= mij) Set_Value(Tree->Left, a, mij, poz, val);
   else Set_Value(Tree->Right, mij+1, b, poz, val);

   JoinSons(Tree);
}

void UpdateMinimal (Node *Tree, int a, int b, int ua, int ub, int val) {
   Propag(Tree, a, b);

   if (Tree->Max < val) return;

   if (ua <= a && b <= ub) {
      if (Tree->Second_Max < val && val <= Tree->Max) {
         Change_Value(Tree, val);

         Propag(Tree, a, b);
         return;
      }
   }

   int mij = (a + b) / 2;

   if (ua <= mij) UpdateMinimal(Tree->Left, a, mij, ua, ub, val);
   if (mij < ub) UpdateMinimal(Tree->Right, mij+1, b, ua, ub, val);

   JoinSons(Tree);
}

void Update (Node *Tree, int a, int b, int ua, int ub, int &cnt, int val) {
   if (Tree == nullptr) return;
   if (Tree->Max <= val) return;
   if (cnt == 0) return;

   Propag(Tree, a, b);

   if (ua <= a && b <= ub) {
      if (Tree->Second_Max < val && val < Tree->Max && Tree->freq <= cnt) {
         cnt -= Tree->freq;
         Change_Value(Tree, val);

         Propag(Tree, a, b);
         return;
      }
   }

   if (a == b) return;

   int mij = (a + b) / 2;

   if (ua <= mij) Update(Tree->Left, a, mij, ua, ub, cnt, val);
   if (mij < ub) Update(Tree->Right, mij+1, b, ua, ub, cnt, val);

   JoinSons(Tree);
}

Node FindSegment (Node *Tree, int a, int b, int qa, int qb) {
   Propag(Tree, a, b);
   if (qa <= a && b <= qb) return *Tree;

   int mij = (a + b) / 2;
   Node st, dr;

   if (qa <= mij && mij < qb)
      return JoinNodes(FindSegment(Tree->Left, a, mij, qa, qb), FindSegment(Tree->Right, mij+1, b, qa, qb));
   else if (qa <= mij) return FindSegment(Tree->Left, a, mij, qa, qb);
   else return FindSegment(Tree->Right, mij+1, b, qa, qb);
}

LL Answer (Node *Tree, int a, int b, int qa, int qb) {
   Propag(Tree, a, b);

   if (qa <= a && b <= qb) return Tree->sum;

   int mij = (a + b) / 2;
   LL ans_st = 0, ans_dr = 0;

   if (qa <= mij) ans_st = Answer(Tree->Left, a, mij, qa, qb);
   if (mij < qb) ans_dr = Answer(Tree->Right, mij+1, b, qa, qb);

   return ans_st + ans_dr;
}

Node *SegTree = new Node;

void initialise(int N, int Q, int h[]) {
   Size = N;
   Init(SegTree, 1, N);

   for (int i = 1; i <= N; ++ i )
      Set_Value(SegTree, 1, N, i, h[i]);
}

void cut(int l, int r, int k) {
   Node value = FindSegment(SegTree, 1, Size, l, r);

   while (k > 0 && value.Max > 0 && 1LL * value.freq * (value.Max - max(0, value.Second_Max)) <= 1LL * k) {
      UpdateMinimal(SegTree, 1, Size, l, r, max(0,value.Second_Max));

      k -= 1LL * value.freq * (value.Max - max(0, value.Second_Max));

      value = FindSegment(SegTree, 1, Size, l, r);
   }

   if (value.Max > 0) {
      int cat_scad = k / value.freq;

      k = k % value.freq;

      UpdateMinimal(SegTree, 1, Size, l, r, max(0, value.Max - cat_scad));

      value.Max -= cat_scad;
      if (value.Max > 0) Update(SegTree, 1, Size, l, r, k, value.Max - 1);
   }
}

void magic(int i, int x) {
   Set_Value(SegTree, 1, Size, i, x);
}

long long int inspect(int l, int r) {
   return Answer(SegTree, 1, Size, l, r);
}

/*
3 4
1 2 3
1 1 3 2
2 1 1000
1 1 3 3
3 1 3
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 74 ms 8188 KB Output is correct
4 Correct 110 ms 8144 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 444 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 589 ms 31288 KB Output is correct
4 Correct 503 ms 31776 KB Output is correct
5 Correct 581 ms 30672 KB Output is correct
6 Correct 454 ms 30304 KB Output is correct
7 Correct 22 ms 8212 KB Output is correct
8 Correct 39 ms 8660 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8212 KB Output is correct
2 Correct 39 ms 8660 KB Output is correct
3 Correct 193 ms 33068 KB Output is correct
4 Correct 207 ms 34332 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 74 ms 8188 KB Output is correct
4 Correct 110 ms 8144 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 22 ms 8212 KB Output is correct
8 Correct 39 ms 8660 KB Output is correct
9 Correct 77 ms 10140 KB Output is correct
10 Correct 85 ms 9880 KB Output is correct
11 Correct 84 ms 9876 KB Output is correct
12 Correct 88 ms 10404 KB Output is correct
13 Correct 80 ms 10548 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 74 ms 8188 KB Output is correct
4 Correct 110 ms 8144 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 589 ms 31288 KB Output is correct
8 Correct 503 ms 31776 KB Output is correct
9 Correct 581 ms 30672 KB Output is correct
10 Correct 454 ms 30304 KB Output is correct
11 Correct 193 ms 33068 KB Output is correct
12 Correct 207 ms 34332 KB Output is correct
13 Correct 77 ms 10140 KB Output is correct
14 Correct 85 ms 9880 KB Output is correct
15 Correct 84 ms 9876 KB Output is correct
16 Correct 88 ms 10404 KB Output is correct
17 Correct 80 ms 10548 KB Output is correct
18 Correct 22 ms 8212 KB Output is correct
19 Correct 39 ms 8660 KB Output is correct
20 Correct 454 ms 36308 KB Output is correct
21 Correct 486 ms 38788 KB Output is correct
22 Correct 448 ms 38232 KB Output is correct
23 Correct 456 ms 38176 KB Output is correct
24 Correct 405 ms 37392 KB Output is correct