oj.uz

Submission #641037

# Submission time Handle Problem Language Result Execution time Memory
641037 2022-09-15T19:10:26 Z Alexandruabcde Weirdtree (RMI21_weirdtree) C++14
21 / 100
 2000 ms 31880 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 64 ms 8212 KB Output is correct
4 Correct 93 ms 8088 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 2 ms 340 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 2 ms 340 KB Output is correct
3 Correct 1149 ms 31276 KB Output is correct
4 Correct 417 ms 31880 KB Output is correct
5 Correct 1288 ms 30648 KB Output is correct
6 Correct 411 ms 30412 KB Output is correct
7 Correct 20 ms 8148 KB Output is correct
8 Execution timed out 2086 ms 8176 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8148 KB Output is correct
2 Execution timed out 2086 ms 8176 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 340 KB Output is correct
3 Correct 64 ms 8212 KB Output is correct
4 Correct 93 ms 8088 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 20 ms 8148 KB Output is correct
8 Execution timed out 2086 ms 8176 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 340 KB Output is correct
3 Correct 64 ms 8212 KB Output is correct
4 Correct 93 ms 8088 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1149 ms 31276 KB Output is correct
8 Correct 417 ms 31880 KB Output is correct
9 Correct 1288 ms 30648 KB Output is correct
10 Correct 411 ms 30412 KB Output is correct
11 Correct 20 ms 8148 KB Output is correct
12 Execution timed out 2086 ms 8176 KB Time limit exceeded
13 Halted 0 ms 0 KB -