Submission #1207263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207263		simplemind_31	Wall (IOI14_wall)	C++20	0 / 100	0 ms	320 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int N,tiempo=-1e9;
vector<pair<int,int>> segmentres;
vector<pair<int,int>> lazy[2]; // valor,tiempo
void propagate(int node,int l,int r){
  if(lazy[0][node].first!=-1 && lazy[1][node].first!=-1 && lazy[0][node].first>lazy[1][node].first){
    if(lazy[0][node].second<lazy[1][node].second){
      lazy[0][node].first=lazy[1][node].first;
    }else{
      lazy[1][node].first=lazy[0][node].first;
    }
  }
  if(l==r){
    if(lazy[0][node].first!=-1){
      segmentres[node].second=lazy[0][node].first;
    }
    if(lazy[1][node].first!=-1){
      segmentres[node].first=lazy[1][node].first;
    }
    return;
  }
  int hiji=2*node+1,hijd=2*node+2;
  if(lazy[0][node].first!=-1){
    segmentres[node].second=lazy[0][node].first;
    lazy[0][hiji].first=max(lazy[0][hiji].first,lazy[0][node].first);
    lazy[0][hijd].first=max(lazy[0][hijd].first,lazy[0][node].first);
    lazy[0][hiji].second=tiempo++;
    lazy[0][hijd].second=tiempo++;
  }
  if(lazy[1][node].first!=-1){
    segmentres[node].first=lazy[1][node].first;
    lazy[1][hiji].first=min(lazy[1][hiji].first,lazy[1][node].first);
    lazy[1][hijd].first=min(lazy[1][hijd].first,lazy[1][node].first);
    lazy[1][hiji].second=tiempo++;
    lazy[1][hijd].second=tiempo++;
  }
  lazy[0][node].first=lazy[1][node].first=-1;
}
pair<int,int> query(int node,int l,int r,int i,int j){
  if(j<l || r<i){
    return {-1e9,1e9};
  }
  propagate(node,l,r);
  if(i<=l && r<=j){
    return segmentres[node];
  }
  int hiji=2*node+1,hijd=2*node+2,mid=(l+r)>>1;
  pair<int,int> fir=query(hiji,l,mid,i,j),sec=query(hijd,mid+1,r,i,j);
  return {max(fir.first,sec.first),min(fir.second,sec.second)};
}
void update(int node,int l,int r,int i,int j,int val,int tipo){
  propagate(node,l,r);
  int mid=(l+r)>>1,hiji=2*node+1,hijd=2*node+2;
  if(i==l && j==r){
    pair<int,int> ans=query(node,l,r,i,j);
    if(tipo==1){
      if(ans.first<=val){
        lazy[0][node].first=val;
        lazy[0][node].second=tiempo++;
      }
    }else{
      if(ans.second>=val){
        lazy[1][node].first=val;
        lazy[1][node].second=tiempo++;
      }
    }
  }
  if(i<=mid){
    update(hiji,l,mid,i,mid,val,tipo);
  }
  if(j>mid){
    update(hijd,mid+1,j,mid+1,r,val,tipo);
  }
  segmentres[node].first=max(segmentres[hiji].first,segmentres[hijd].first);
  segmentres[node].second=min(segmentres[hiji].second,segmentres[hijd].second);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n;
  segmentres.assign(4*n+5,{0,0});
  lazy[0].assign(4*n+5,{-1,tiempo});
  lazy[1]=lazy[0];
  for(int i=0;i<k;i++){
    update(0,0,n-1,left[i],right[i],height[i],op[i]);
  }
  return;
}

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