Submission #1026715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026715		dozer	Wall (IOI14_wall)	C++14	61 / 100	3081 ms	88920 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define sp " "
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt","w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define ll long long
#define MAXN 2000005

const int modulo = 1e9 + 7;
const ll INF = 2e18 +7;


pii mini[4 * MAXN], maks[4 * MAXN];



void push(int node, int l, int r){
  if (l == r) return;
  vector<array<int, 3>> v;

  //cout<<"push : "<<l<<sp<<r<<sp<<maks[node].st<<sp<<mini[node].st<<endl;
  v.pb({maks[node].nd, maks[node].st, 1});
  v.pb({mini[node].nd, mini[node].st, 2});
  sort(v.begin(), v.end());
  vector<int> child = {LL, RR};

  for (auto i : v){
    int type = i[2], val = i[1], time = i[0];
   // cout<<"!! "<<type<<sp<<val<<sp<<time<<endl;
    for (auto gh : child){
      if (type == 1){ // max
        if (maks[gh].st <= val){
          maks[gh] = {val, time};
          if (mini[gh].st <= val)
            mini[gh] = maks[gh];
        }
      }

      else{
        if (mini[gh].st >= val){
          mini[gh] = {val, time};
          if (maks[gh].st >= val){
            maks[gh] = mini[gh];
          }
        }
      }
      //cout<<"pushed : "<<maks[gh].st<<sp<<mini[gh].st<<endl;
    }
  }

  mini[node] = {modulo, 0};
  maks[node] = {0, 0};
}

void build(int node, int l, int r){
  maks[node] = {0, 0};
  mini[node] = {modulo, 0};
  if (l == r) return;
  build(LL, l, mid);
  build(RR, mid + 1, r);
}


void update(int node, int l, int r, int sl, int sr, int val, int time, int type){
  push(node, l, r);
 // cout<<l<<sp<<r<<endl;
  if (l > sr || r < sl) return;
  if (l >= sl && r <= sr){
    if (type == 1){ //max operation
      if (maks[node].st <= val){
        maks[node] = {val, time};
        if (mini[node].st <= val) mini[node] = maks[node];
      }
    }
    else{
      if (mini[node].st >= val){
        mini[node] = {val, time};
        if (maks[node].st >= val) maks[node] = mini[node];
      }
    }
    return;
  }

  update(LL, l, mid, sl, sr, val, time, type);
  update(RR, mid + 1, r, sl, sr, val, time, type);
}



int query(int node, int l, int r, int sl){
  push(node, l, r);
  if (l == r) {
    return maks[node].st;
  }
  if (sl <= mid) return query(LL, l, mid, sl);
  return query(RR, mid + 1, r, sl);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  build(1, 1, n);
  
  for (int i = 0; i < k; i++){
    left[i]++, right[i]++;
    update(1, 1, n, left[i], right[i], height[i], i, op[i]);
  }

  for (int j = 1; j <= n; j++){
    finalHeight[j - 1] = query(1, 1, n, j);
  } 
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39