oj.uz

Submission #291070

# Submission time Handle Problem Language Result Execution time Memory
291070 2020-09-04T16:03:31 Z davi_bart Wall (IOI14_wall) C++14
100 / 100
 1761 ms 173212 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 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 11 ms 1664 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 192 ms 8280 KB Output is correct
3 Correct 121 ms 5860 KB Output is correct
4 Correct 285 ms 17400 KB Output is correct
5 Correct 287 ms 17892 KB Output is correct
6 Correct 297 ms 18040 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 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 10 ms 1664 KB Output is correct
5 Correct 11 ms 1636 KB Output is correct
6 Correct 10 ms 1664 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 187 ms 8184 KB Output is correct
9 Correct 114 ms 6008 KB Output is correct
10 Correct 268 ms 17404 KB Output is correct
11 Correct 269 ms 17912 KB Output is correct
12 Correct 293 ms 17932 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 193 ms 8328 KB Output is correct
15 Correct 49 ms 3192 KB Output is correct
16 Correct 919 ms 17668 KB Output is correct
17 Correct 504 ms 17656 KB Output is correct
18 Correct 461 ms 17788 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 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 416 KB Output is correct
8 Correct 180 ms 8280 KB Output is correct
9 Correct 108 ms 5880 KB Output is correct
10 Correct 281 ms 17400 KB Output is correct
11 Correct 260 ms 17912 KB Output is correct
12 Correct 286 ms 18040 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 186 ms 8184 KB Output is correct
15 Correct 48 ms 3192 KB Output is correct
16 Correct 955 ms 17668 KB Output is correct
17 Correct 463 ms 17784 KB Output is correct
18 Correct 486 ms 17680 KB Output is correct
19 Correct 1595 ms 165660 KB Output is correct
20 Correct 1510 ms 170668 KB Output is correct
21 Correct 1551 ms 173116 KB Output is correct
22 Correct 1562 ms 170584 KB Output is correct
23 Correct 1551 ms 170528 KB Output is correct
24 Correct 1565 ms 170512 KB Output is correct
25 Correct 1761 ms 170392 KB Output is correct
26 Correct 1593 ms 173192 KB Output is correct
27 Correct 1697 ms 173212 KB Output is correct
28 Correct 1575 ms 170792 KB Output is correct
29 Correct 1553 ms 170784 KB Output is correct
30 Correct 1536 ms 170776 KB Output is correct