oj.uz

Submission #291074

# Submission time Handle Problem Language Result Execution time Memory
291074 2020-09-04T16:05:40 Z davi_bart Wall (IOI14_wall) C++14
100 / 100
 1598 ms 166076 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;


#define N 2000003

class SegmentTree {
  const int inf = 1e9;
  int n, n0;
  int max_v[4*N], smax_v[4*N], max_c[4*N];
  int min_v[4*N], smin_v[4*N], min_c[4*N];
  int sum[4*N];
  int ecnt[4*N], ladd[4*N];

  void update_node_max(int k, int x) {
    sum[k] += (x - max_v[k]) * max_c[k];

    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(max_v[k] == smin_v[k]) {
      max_v[k] = smin_v[k] = x;
    } else {
      max_v[k] = x;
    }
  }
  void update_node_min(int k, int x) {
    sum[k] += (x - min_v[k]) * min_c[k];

    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(smax_v[k] == min_v[k]) {
      min_v[k] = smax_v[k] = x;
    } else {
      min_v[k] = x;
    }
  }

  void push(int k) {

    if(ladd[k]) {
      addaint(2*k+1, ladd[k]);
      addaint(2*k+2, ladd[k]);
      ladd[k] = 0;
    }

    if(max_v[k] < max_v[2*k+1]) {
      update_node_max(2*k+1, max_v[k]);
    }
    if(min_v[2*k+1] < min_v[k]) {
      update_node_min(2*k+1, min_v[k]);
    }

    if(max_v[k] < max_v[2*k+2]) {
      update_node_max(2*k+2, max_v[k]);
    }
    if(min_v[2*k+2] < min_v[k]) {
      update_node_min(2*k+2, min_v[k]);
    }
  }

  void update(int k) {
    sum[k] = sum[2*k+1] + sum[2*k+2];

    if(max_v[2*k+1] < max_v[2*k+2]) {
      max_v[k] = max_v[2*k+2];
      max_c[k] = max_c[2*k+2];
      smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
    } else if(max_v[2*k+1] > max_v[2*k+2]) {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1];
      smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
    } else {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1] + max_c[2*k+2];
      smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
    }

    if(min_v[2*k+1] < min_v[2*k+2]) {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1];
      smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]);
    } else if(min_v[2*k+1] > min_v[2*k+2]) {
      min_v[k] = min_v[2*k+2];
      min_c[k] = min_c[2*k+2];
      smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]);
    } else {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1] + min_c[2*k+2];
      smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]);
    }
  }

  void _update_min(int x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || max_v[k] <= x) {
      return;
    }
    if(a <= l && r <= b && smax_v[k] < x) {
      update_node_max(k, x);
      return;
    }

    push(k);
    _update_min(x, a, b, 2*k+1, l, (l+r)/2);
    _update_min(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  void _update_max(int x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || x <= min_v[k]) {
      return;
    }
    if(a <= l && r <= b && x < smin_v[k]) {
      update_node_min(k, x);
      return;
    }

    push(k);
    _update_max(x, a, b, 2*k+1, l, (l+r)/2);
    _update_max(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }

  void addaint(int k, int x) {
    max_v[k] += x; smax_v[k] += x;
    min_v[k] += x; smin_v[k] += x;

    sum[k] += ecnt[k] * x;
    ladd[k] += x;
  }

  /*void _add(int x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      addaint(k, x);
      return;
    }

    push(k);
    _add(x, a, b, 2*k+1, l, (l+r)/2);
    _add(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }*/

  int _query_max(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return max_v[k];
    }
    push(k);
    int lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
    int rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }

  int _query_min(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return inf;
    }
    if(a <= l && r <= b) {
      return min_v[k];
    }
    push(k);
    int lv = _query_min(a, b, 2*k+1, l, (l+r)/2);
    int rv = _query_min(a, b, 2*k+2, (l+r)/2, r);
    return min(lv, rv);
  }

  /*int _query_sum(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return 0;
    }
    if(a <= l && r <= b) {
      return sum[k];
    }
    push(k);
    int lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
    int rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
    return lv + rv;
  }*/

public:
  SegmentTree(int n) {
    SegmentTree(n, nullptr);
  }

  SegmentTree(int n, int *a) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;

    if(a != nullptr) {
      for(int i=0; i<n; ++i) {
        max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = a[i];
        smax_v[n0-1+i] = -inf;
        smin_v[n0-1+i] = inf;
        max_c[n0-1+i] = min_c[n0-1+i] = 1;

        ecnt[n0-1+i] = 1; ladd[n0-1+i] = 0;
      }
    } else {
      for(int i=n; i<n0; ++i) {
        max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = 0;
        smax_v[n0-1+i] = -inf;
        smin_v[n0-1+i] = inf;
        max_c[n0-1+i] = min_c[n0-1+i] = 1;

        ecnt[n0-1+i] = 1; ladd[n0-1+i] = 0;
      }
    }
    for(int i=n; i<n0; ++i) {
      max_v[n0-1+i] = smax_v[n0-1+i] = 0;
      min_v[n0-1+i] = smin_v[n0-1+i] = 0;
      max_c[n0-1+i] = min_c[n0-1+i] = 0;

      ecnt[n0-1+i] = ladd[n0-1+i] = 0;
    }
    for(int i=n0-2; i>=0; i--) {
      update(i);
      ecnt[i] = ecnt[2*i+1] + ecnt[2*i+2];
    }
  }

  void update_min(int a, int b, int x) {
    _update_min(x, a, b, 0, 0, n0);
  }

  void update_max(int a, int b, int x) {
    _update_max(x, a, b, 0, 0, n0);
  }

  /*void add(int a, int b, int x) {
    _add(x, a, b, 0, 0, n0);
  }*/

  int query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }

  int query_min(int a, int b) {
    return _query_min(a, b, 0, 0, n0);
  }

 /* int query_sum(int a, int b) {
    return _query_sum(a, b, 0, 0, n0);
  }*/
};
/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412*/
int v[N];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  SegmentTree stb(n+1, v);
  for(int i=0;i<k;i++){
    if(op[i]==1){
      stb.update_max(left[i],right[i]+1,height[i]);
    }else{
      stb.update_min(left[i],right[i]+1,height[i]);
    }
  }
  for(int i=0;i<n;i++){
    finalHeight[i]=stb.query_max(i,i+1);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 11 ms 1724 KB Output is correct
5 Correct 9 ms 1664 KB Output is correct
6 Correct 9 ms 1664 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 184 ms 8796 KB Output is correct
3 Correct 112 ms 6392 KB Output is correct
4 Correct 259 ms 17912 KB Output is correct
5 Correct 265 ms 18552 KB Output is correct
6 Correct 294 ms 18552 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 10 ms 1664 KB Output is correct
5 Correct 9 ms 1664 KB Output is correct
6 Correct 9 ms 1664 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 188 ms 8824 KB Output is correct
9 Correct 112 ms 6136 KB Output is correct
10 Correct 263 ms 18040 KB Output is correct
11 Correct 263 ms 18424 KB Output is correct
12 Correct 294 ms 18484 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 187 ms 8440 KB Output is correct
15 Correct 49 ms 3576 KB Output is correct
16 Correct 968 ms 18108 KB Output is correct
17 Correct 462 ms 18168 KB Output is correct
18 Correct 476 ms 18168 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 10 ms 1792 KB Output is correct
6 Correct 9 ms 1664 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 199 ms 8824 KB Output is correct
9 Correct 115 ms 6136 KB Output is correct
10 Correct 260 ms 18040 KB Output is correct
11 Correct 265 ms 18552 KB Output is correct
12 Correct 300 ms 18424 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 201 ms 8568 KB Output is correct
15 Correct 53 ms 3448 KB Output is correct
16 Correct 985 ms 18108 KB Output is correct
17 Correct 484 ms 18180 KB Output is correct
18 Correct 467 ms 18296 KB Output is correct
19 Correct 1557 ms 166076 KB Output is correct
20 Correct 1502 ms 163392 KB Output is correct
21 Correct 1541 ms 165872 KB Output is correct
22 Correct 1521 ms 163400 KB Output is correct
23 Correct 1563 ms 163384 KB Output is correct
24 Correct 1554 ms 163576 KB Output is correct
25 Correct 1576 ms 163140 KB Output is correct
26 Correct 1584 ms 165568 KB Output is correct
27 Correct 1590 ms 165544 KB Output is correct
28 Correct 1557 ms 162972 KB Output is correct
29 Correct 1598 ms 163068 KB Output is correct
30 Correct 1552 ms 163064 KB Output is correct