Submission #610969

#	Time	Username	Problem	Language	Result	Execution time	Memory
610969		APROHACK	Wall (IOI14_wall)	C++14	61 / 100	3072 ms	35056 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll N, K, blocksz;
vector<ll>ans, ans2;
vector<ll>values;
ll block[1500][2]; // minimo, maximo
void updateThis(ll blc){
  for(int i = blc*blocksz ; i < (blc+1)*blocksz ; i++){
    if(values[i]<=block[blc][0])values[i] = block[blc][0];
    if(values[i]>=block[blc][1])values[i] = block[blc][1];
    //cout << i << " =  " << values[i] << endl;
  }
  block[blc][0]=0;
  block[blc][1]=1000000000;
}
void push(ll l, ll r, ll op, ll curr){
  int currentBlock = l/blocksz, lastblock = r/blocksz;
  updateThis(currentBlock);

  for(int i = l ; i < min((currentBlock+1)*blocksz, r+1) ; i++){
    if(op==1)values[i] = max(values[i], curr);
    else values[i] = min(values[i], curr);
  }
  for(int i = currentBlock+1 ; i < lastblock ; i++){
    if(op==1){
      if(block[i][0]<curr){
        //cout<< " block" << i << " min " << curr << endl;
        block[i][0]=curr;
        block[i][1]=max(curr, block[i][1]);
      }
    }else{
      if(block[i][1]>curr){
        //cout<< " block" << i << " max " << curr << endl;
        block[i][1]=curr;
        block[i][0]=min(block[i][0], curr);
      }
    }
  }
  if(currentBlock == lastblock)return ;
  updateThis(lastblock);
  for(int i = lastblock*blocksz ; i <= r ; i++){
    if(op==1)values[i] = max(values[i], curr);
    else values[i] = min(values[i], curr);
    //cout<<"ed " << i << " ";
  }
  //cout << endl;



}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n, K=k;
  for(int i = 0 ; i < n ; i ++){
    values.pb(0);
  }


  blocksz = sqrt(n);
  for(int i = 0 ; i < blocksz+1 ; i++){
    block[i][0]=0;
    block[i][1]=1000000000;
  }
  for(int  i = 0 ; i < k ; i++){
    push(left[i], right[i], op[i], height[i]);
  }
  for(int i = 0 ; i < blocksz +1 ; i++){
    updateThis(i);
  }
  for(int i = 0 ; i < n ; i ++)finalHeight[i] = values[i];


  return;
}

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