oj.uz

Submission #291076

# Submission time Handle Problem Language Result Execution time Memory
291076 2020-09-04T16:06:38 Z davi_bart Wall (IOI14_wall) C++14
100 / 100
 1566 ms 165696 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 0 ms 384 KB Output is correct
2 Correct 2 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 1792 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 181 ms 8184 KB Output is correct
3 Correct 109 ms 5880 KB Output is correct
4 Correct 266 ms 17596 KB Output is correct
5 Correct 266 ms 18040 KB Output is correct
6 Correct 292 ms 17912 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 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 384 KB Output is correct
8 Correct 183 ms 8184 KB Output is correct
9 Correct 111 ms 5880 KB Output is correct
10 Correct 263 ms 17400 KB Output is correct
11 Correct 269 ms 18040 KB Output is correct
12 Correct 292 ms 17912 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 190 ms 8312 KB Output is correct
15 Correct 48 ms 3192 KB Output is correct
16 Correct 913 ms 17784 KB Output is correct
17 Correct 458 ms 17784 KB Output is correct
18 Correct 455 ms 17784 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 2 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 0 ms 384 KB Output is correct
8 Correct 184 ms 8184 KB Output is correct
9 Correct 108 ms 6008 KB Output is correct
10 Correct 259 ms 17480 KB Output is correct
11 Correct 261 ms 17912 KB Output is correct
12 Correct 297 ms 17912 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 190 ms 8184 KB Output is correct
15 Correct 47 ms 3192 KB Output is correct
16 Correct 907 ms 17728 KB Output is correct
17 Correct 458 ms 17656 KB Output is correct
18 Correct 464 ms 17788 KB Output is correct
19 Correct 1566 ms 165532 KB Output is correct
20 Correct 1525 ms 163196 KB Output is correct
21 Correct 1524 ms 165532 KB Output is correct
22 Correct 1524 ms 163320 KB Output is correct
23 Correct 1510 ms 163192 KB Output is correct
24 Correct 1520 ms 163192 KB Output is correct
25 Correct 1529 ms 163176 KB Output is correct
26 Correct 1539 ms 165696 KB Output is correct
27 Correct 1552 ms 165532 KB Output is correct
28 Correct 1516 ms 163064 KB Output is correct
29 Correct 1512 ms 163192 KB Output is correct
30 Correct 1510 ms 163192 KB Output is correct