oj.uz

Submission #828903

# Submission time Handle Problem Language Result Execution time Memory
828903 2023-08-17T19:36:17 Z beaconmc Wall (IOI14_wall) C++14
0 / 100
 244 ms 112432 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]);
  }
}

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] = 0;
  }
  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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 98752 KB Output is correct
2 Correct 40 ms 98828 KB Output is correct
3 Incorrect 39 ms 98808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98872 KB Output is correct
2 Correct 244 ms 112432 KB Output is correct
3 Incorrect 163 ms 105928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98796 KB Output is correct
2 Correct 40 ms 98892 KB Output is correct
3 Incorrect 39 ms 98768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 98732 KB Output is correct
2 Correct 41 ms 98888 KB Output is correct
3 Incorrect 40 ms 98772 KB Output isn't correct
4 Halted 0 ms 0 KB -