oj.uz

답안 #640918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640918 2022-09-15T14:21:37 Z Alexandruabcde Weirdtree (RMI21_weirdtree) C++14
21 / 100
 2000 ms 31972 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);
}

/*
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 88 ms 8200 KB Output is correct
4 Correct 105 ms 8072 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1263 ms 31204 KB Output is correct
4 Correct 465 ms 31972 KB Output is correct
5 Correct 1340 ms 30660 KB Output is correct
6 Correct 418 ms 30396 KB Output is correct
7 Correct 21 ms 8148 KB Output is correct
8 Execution timed out 2076 ms 8148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8148 KB Output is correct
2 Execution timed out 2076 ms 8148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 88 ms 8200 KB Output is correct
4 Correct 105 ms 8072 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 21 ms 8148 KB Output is correct
8 Execution timed out 2076 ms 8148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 88 ms 8200 KB Output is correct
4 Correct 105 ms 8072 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1263 ms 31204 KB Output is correct
8 Correct 465 ms 31972 KB Output is correct
9 Correct 1340 ms 30660 KB Output is correct
10 Correct 418 ms 30396 KB Output is correct
11 Correct 21 ms 8148 KB Output is correct
12 Execution timed out 2076 ms 8148 KB Time limit exceeded
13 Halted 0 ms 0 KB -