Submission #1017667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017667		dosts	Wall (IOI14_wall)	C++17	100 / 100	1464 ms	151724 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(xx) xx.begin(),xx.end()


  pii propmini(pii state,int minimise) {
    if (minimise == -1) return state;
    if (state.ss != -1) {
      if (state.ss <= minimise) return state;
    }
    if (state.ff < minimise) return {state.ff,minimise};
    return {minimise,minimise};
  }

  pii propmaxi(pii state,int maximise) {
    if (maximise == -1) return state;
    if (state.ff == -1) {
      if (state.ss != -1 && state.ss <= maximise) return {maximise,maximise};
      return {maximise,state.ss};
    }
    if (state.ss == -1) {
      if (state.ff >= maximise) return state;
      return {maximise,state.ss};
    }
    if (maximise < state.ff) return state;
    if (maximise > state.ss) return {maximise,maximise};
    return {maximise,state.ss};
  }

struct ST {
  vector<pii> lazy;
  vector<pii> t;

  ST(int nn) {
    lazy.assign(4*nn+1,pii{-1,-1});
    t.assign(4*nn+1,pii{-1,-1});
  }


  void push(int node,bool leaf) {
    t[node] = propmaxi(t[node],lazy[node].ff);
    t[node] = propmini(t[node],lazy[node].ss);
    if (!leaf) {
      lazy[2*node] = propmaxi(lazy[2*node],lazy[node].ff);
      lazy[2*node] = propmini(lazy[2*node],lazy[node].ss);
      lazy[2*node+1] = propmaxi(lazy[2*node+1],lazy[node].ff);
      lazy[2*node+1] = propmini(lazy[2*node+1],lazy[node].ss);
    }
    lazy[node] = {-1,-1};
  }

  void mini(int node,int l,int r,int L,int R,int v) {
    push(node,l==r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
      lazy[node] = propmini(lazy[node],v);
      push(node,l==r);
      return;
    }
    int m = (l+r) >> 1;
    mini(2*node,l,m,L,R,v);
    mini(2*node+1,m+1,r,L,R,v);
  }
  void maxi(int node,int l,int r,int L,int R,int v) {
    push(node,l==r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
      lazy[node] = propmaxi(lazy[node],v);
      push(node,l==r);
      return;
    }
    int m = (l+r) >> 1;
    maxi(2*node,l,m,L,R,v);
    maxi(2*node+1,m+1,r,L,R,v);
  }
  pii query(int node,int l,int r,int p) {
    push(node,l==r);
    if (l == r) return t[node];
    int m = (l+r) >> 1;
    if (p<=m) return query(2*node,l,m,p);
    return query(2*node+1,m+1,r,p);
  }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  ST st(n);
  pii p = {-1,-1};
  for (int i=0;i<k;i++){
    if (op[i] == 1) {
      //ADD
      st.maxi(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    else {
      //REM
      st.mini(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
  }

  for (int i=0;i<n;i++) {
    pii p = st.query(1,1,n,i+1);
    if (p.ff!=-1) finalHeight[i] = p.ff;
    else finalHeight[i] = 0;
  }
  return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:95:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   95 |   pii p = {-1,-1};
      |       ^

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