Submission #545797

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
545797	2022-04-05 13:04:03	amunduzbaev	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	649 ms	72468 KiB

street_lamps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
  int y, val, sz, c, sum;
  node *lx, *rx;
  
  node(int x, int v) : val(x), sz(1), c(v), sum(v), lx(NULL), rx(NULL){
    y = uniform_int_distribution<int>(0, 2e9)(rng);
  }
};
struct rbst{
  void rec(node* a){
    a->sum = (a->lx != NULL ? a->lx->sum : 0) + (a->rx != NULL ? a->rx->sum : 0) + a->c;
  }
  node* merge(node* a, node* b){
    if(a == NULL) return b;
    if(b == NULL) return a;
    
    if(a->y > b->y){
      a->rx = merge(a->rx, b);
      rec(a);
      return a;
    } else {
      b->lx = merge(a, b->lx);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20