Submission #139949

#	Time	Username	Problem	Language	Result	Execution time	Memory
139949		MrBrionix	Wall (IOI14_wall)	C++14	100 / 100	739 ms	115120 KiB

wall

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define INF 100005

int v[2000005],l,r;
pair<int,int> q;
pair<int,int> rt[9000000];

inline pair<int,int> unite(pair<int,int> a,pair<int,int> b){
    pair<int,int> tmp;
    
    tmp.second=max(b.first,min(b.second,a.second));
    tmp.first=min(b.second,max(b.first,a.first));
    
    return tmp;    
}

inline void push(int pos){
    
    rt[pos*2]=unite(rt[pos],rt[pos*2]);
    rt[pos*2+1]=unite(rt[pos],rt[pos*2+1]);
    
    rt[pos]={0,INF};  
}

void upd(int pos,int _l,int _r){

    if(r<_l || l>_r)return;
    
    if(_l>=l && _r<=r){
        rt[pos]=unite(q,rt[pos]);
        return;    
    }
    
    push(pos);
    
    upd(pos*2,_l,(_l+_r)/2);
    upd(pos*2+1,(_l+_r)/2+1,_r);
}

void query(int pos,int _l,int _r,int val){

    if(val<rt[pos].first)val=rt[pos].first;
    if(val>rt[pos].second)val=rt[pos].second;

    if(_l==_r){
        v[_l]=val;
        return;    
    }
    
    query(pos*2,_l,(_l+_r)/2,val);
    query(pos*2+1,(_l+_r)/2+1,_r,val);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
    for(int i=0;i<9000000;i++)rt[i].second=INF;
    
    
    for(int i=k-1;i>=0;i--){   
        l=left[i];
        r=right[i];
        if(op[i]==1){
            q.first=height[i];
            q.second=INF; 
        }
        else{
            q.first=0;
            q.second=height[i];    
        }
        
        upd(1,0,n-1);
    }
    
    query(1,0,n-1,0);
  
    for(int i=0;i<n;i++){
    finalHeight[i]=v[i];   
    }
  
    return;
}
/*
int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}*/

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