oj.uz

Submission #640917

# Submission time Handle Problem Language Result Execution time Memory
640917 2022-09-15T14:16:14 Z Alexandruabcde Weirdtree (RMI21_weirdtree) C++14
21 / 100
 2000 ms 39612 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 (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 -= 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);
}

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 344 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 344 KB Output is correct
3 Correct 68 ms 10132 KB Output is correct
4 Correct 99 ms 10044 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 1181 ms 38852 KB Output is correct
4 Correct 424 ms 39612 KB Output is correct
5 Correct 1291 ms 38208 KB Output is correct
6 Correct 418 ms 37804 KB Output is correct
7 Correct 21 ms 8148 KB Output is correct
8 Execution timed out 2088 ms 8140 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8148 KB Output is correct
2 Execution timed out 2088 ms 8140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 68 ms 10132 KB Output is correct
4 Correct 99 ms 10044 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 21 ms 8148 KB Output is correct
8 Execution timed out 2088 ms 8140 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 68 ms 10132 KB Output is correct
4 Correct 99 ms 10044 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1181 ms 38852 KB Output is correct
8 Correct 424 ms 39612 KB Output is correct
9 Correct 1291 ms 38208 KB Output is correct
10 Correct 418 ms 37804 KB Output is correct
11 Correct 21 ms 8148 KB Output is correct
12 Execution timed out 2088 ms 8140 KB Time limit exceeded
13 Halted 0 ms 0 KB -