oj.uz

Submission #828921

# Submission time Handle Problem Language Result Execution time Memory
828921 2023-08-17T20:22:15 Z beaconmc Wall (IOI14_wall) C++14
100 / 100
 501 ms 135208 KB 
#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

const ll N = 1<<21;
ll tree[2*N];
ll mini[2*N];
ll maxi[2*N];

void prop(ll k){

  if (mini[k] <= maxi[k*2]){
    mini[k*2] = mini[k];
    maxi[k*2] = mini[k];
  }else{
    mini[k*2] = min(mini[k*2], mini[k]);
  }
  if (maxi[k] >= mini[k*2]){
    mini[k*2] = maxi[k];
    maxi[k*2] = maxi[k];
  }else{
    maxi[k*2] = max(maxi[k*2], maxi[k]);
  }

  if (mini[k] <= maxi[k*2+1]){
    mini[k*2+1] = mini[k];
    maxi[k*2+1] = mini[k];
  }else{
    mini[k*2+1] = min(mini[k*2+1], mini[k]);
  }
  if (maxi[k] >= mini[k*2+1]){
    mini[k*2+1] = maxi[k];
    maxi[k*2+1] = maxi[k];
  }else{
    maxi[k*2+1] = max(maxi[k*2+1], maxi[k]);
  }
  maxi[k] = -1;
  mini[k] = 1000000000000;
}

void updmax(ll a, ll b, ll val, ll k=1, ll x=0, ll y = N-1){
  if (b<x || a>y) return;

  if (a<=x && y<=b){
    if (val >= mini[k]){
      mini[k] = val;
      maxi[k] = val;
    }else{
      maxi[k] = max(maxi[k], val);
    }
    return;
  }
  prop(k);
  ll mid = (x+y)/2;
  updmax(a, b, val, k*2, x, mid);
  updmax(a, b, val, k*2+1, mid+1, y);
}

void updmin(ll a, ll b, ll val, ll k=1, ll x=0, ll y = N-1){
  if (b<x || a>y) return;

  if (a<=x && y<=b){
    if (val <= maxi[k]){
      mini[k] = val;
      maxi[k] = val;
    }else{
      mini[k] = min(mini[k], val);
    }
    return;
  }
  prop(k);
  ll mid = (x+y)/2;

  updmin(a, b, val, k*2, x, mid);
  updmin(a, b, val, k*2+1, mid+1, y);
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  FOR(i,0,2*N){
    tree[i] = 0;
    mini[i] = 1000000000000;
    maxi[i] = -1;
  }
  FOR(i,0,k){
    if (op[i] == 1){
      updmax(left[i], right[i], height[i]);
    }else{
      updmin(left[i], right[i], height[i]);
    }
  }
  FOR(i,0,N){
    prop(i);
  }

  FOR(i,0,n){
    finalHeight[i] = min((ll) finalHeight[i], mini[N+i]);
    finalHeight[i] = max((ll) finalHeight[i], maxi[N+i]);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98684 KB Output is correct
2 Correct 42 ms 98892 KB Output is correct
3 Correct 50 ms 98808 KB Output is correct
4 Correct 49 ms 99072 KB Output is correct
5 Correct 44 ms 99004 KB Output is correct
6 Correct 44 ms 98936 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98728 KB Output is correct
2 Correct 301 ms 112428 KB Output is correct
3 Correct 161 ms 105880 KB Output is correct
4 Correct 370 ms 116748 KB Output is correct
5 Correct 283 ms 117804 KB Output is correct
6 Correct 250 ms 116264 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98664 KB Output is correct
2 Correct 41 ms 98916 KB Output is correct
3 Correct 40 ms 98732 KB Output is correct
4 Correct 42 ms 98992 KB Output is correct
5 Correct 42 ms 98948 KB Output is correct
6 Correct 43 ms 98976 KB Output is correct
7 Correct 37 ms 98656 KB Output is correct
8 Correct 302 ms 112372 KB Output is correct
9 Correct 172 ms 105956 KB Output is correct
10 Correct 380 ms 116808 KB Output is correct
11 Correct 252 ms 117804 KB Output is correct
12 Correct 251 ms 116260 KB Output is correct
13 Correct 37 ms 98768 KB Output is correct
14 Correct 364 ms 112432 KB Output is correct
15 Correct 62 ms 99920 KB Output is correct
16 Correct 448 ms 117000 KB Output is correct
17 Correct 261 ms 116424 KB Output is correct
18 Correct 257 ms 116392 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98764 KB Output is correct
2 Correct 43 ms 98892 KB Output is correct
3 Correct 45 ms 98732 KB Output is correct
4 Correct 48 ms 98980 KB Output is correct
5 Correct 45 ms 99000 KB Output is correct
6 Correct 44 ms 98980 KB Output is correct
7 Correct 41 ms 98704 KB Output is correct
8 Correct 317 ms 112332 KB Output is correct
9 Correct 160 ms 105888 KB Output is correct
10 Correct 370 ms 116748 KB Output is correct
11 Correct 267 ms 117756 KB Output is correct
12 Correct 251 ms 116244 KB Output is correct
13 Correct 38 ms 98692 KB Output is correct
14 Correct 317 ms 112436 KB Output is correct
15 Correct 70 ms 99916 KB Output is correct
16 Correct 451 ms 117044 KB Output is correct
17 Correct 262 ms 116428 KB Output is correct
18 Correct 258 ms 116420 KB Output is correct
19 Correct 479 ms 135140 KB Output is correct
20 Correct 493 ms 132632 KB Output is correct
21 Correct 485 ms 135064 KB Output is correct
22 Correct 477 ms 132680 KB Output is correct
23 Correct 483 ms 132672 KB Output is correct
24 Correct 486 ms 132560 KB Output is correct
25 Correct 488 ms 132564 KB Output is correct
26 Correct 492 ms 135208 KB Output is correct
27 Correct 501 ms 135112 KB Output is correct
28 Correct 494 ms 132636 KB Output is correct
29 Correct 481 ms 132660 KB Output is correct
30 Correct 500 ms 132572 KB Output is correct