Submission #641042

#	Time	Username	Problem	Language	Result	Execution time	Memory
641042		Alexandruabcde	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	589 ms	38788 KiB

weirdtree

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29