Submission #1237281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237281		lalig777	Wall (IOI14_wall)	C++20	100 / 100	507 ms	104652 KiB

wall

#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
using namespace std;

vector<pair<int,int> >st(1e7, make_pair(0,0));

void add(int p, int l, int r, int a, int b, int h){
  if (p!=1){
    int pare=p/2;
    st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
    st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
  }
  if (a<=l && b>=r){
    st[p].first=max(st[p].first, h);
    st[p].second=max(st[p].second, h);
    return;
  }
  else if (b<l or a>r) return;
  int m=(l+r)/2;
  add(p*2, l, m, a, b, h);
  add(p*2+1, m+1, r, a, b, h);
  st[p].first=min(st[p*2].first, st[p*2+1].first);
  st[p].second=max(st[p*2].second, st[p*2+1].second);
  //cout << "p " << p << " " << l << " " << r << " vals " << st[p].first << " " << st[p].second << "\n";
  return;
}

void remove(int p, int l, int r, int a, int b, int h){
  if (p!=1){
    int pare=p/2;
    st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
    st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
  }
  if (a<=l && b>=r){
    st[p].first=min(st[p].first, h);
    st[p].second=min(st[p].second, h);
    return;
  }
  else if (b<l or a>r) return;
  int m=(l+r)/2;
  remove(p*2, l, m, a, b, h);
  remove(p*2+1, m+1, r, a, b, h);
  st[p].first=min(st[p*2].first, st[p*2+1].first);
  st[p].second=max(st[p*2].second, st[p*2+1].second);
  return;
}

void fin(int p, int l, int r, int* finalHeight){
  if (p!=1){
    int pare=p/2;
    st[p].first=max(min(st[p].first, st[pare].second), st[pare].first);
    st[p].second=min(max(st[p].second, st[pare].first), st[pare].second);
  }
  if (l==r){
    finalHeight[l]=st[p].first;
    return;
  }
  int m=(l+r)/2;
  fin(2*p, l, m, finalHeight);
  fin(2*p+1, m+1, r, finalHeight);
  return;
}

void buildWall (int n, int k, int* op, int* left, int* right, int* height, int* finalHeight){
  for (int i=0; i<k; i++){
    int a=left[i], b=right[i];
    if (op[i]==1) add(1, 0, n-1, a, b, height[i]);
    else remove(1, 0, n-1, a, b, height[i]);
    //fin(1, 0, n-1, finalHeight);
    
  }fin(1, 0, n-1, finalHeight);
  return;
}

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