Submission #1207245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207245		matisito	Wall (IOI14_wall)	C++20	0 / 100	123 ms	82748 KiB

wall

#include "wall.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;


const int maxK=5e5;
struct segtree{
  int n;
  vector<pair<int, int>>st;
  segtree(int n):n(n), st(4*n){};
  void update(int root, int l, int r, pair<int, int>val, int posi){
    if(l==r){
      st[root]=val;
      return;
    }
    int mid=(l+r)/2;
    if(posi<=mid) update(2*root, l, mid, val, posi);
    else update(2*root+1, mid+1, r, val, posi);
    int lefti;
    if(st[2*root].first==-1) lefti=0;
    else lefti=st[2*root].second;
    st[root]=st[2*root];
    if(st[2*root+1].first==1 &&  lefti<=st[2*root+1].second) st[root]=st[2*root+1];
    if(st[2*root+1].first==2 &&  lefti>=st[2*root+1].second) st[root]=st[2*root+1];
  }
}st(maxK+1);

const int maxN=2e6;
struct point{
  int x, y, z;
};

vector<point>v [maxN+5];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0 ; i<4*(maxK+1) ; i++){
    st.st[i]={-1, -1};
  }
  for(int i=0 ; i<k ; i++){
    v[left[i]].push_back({i, op[i], height[i]});
    v[right[i]+1].push_back({i, -op[i], height[i]});
  }
  for(int i=0 ; i<n ; i++){
    for(point it:v[i]){
      if(it.y<0) st.update(1, 0, n-1, make_pair(-1, -1), it.x);
      else st.update(1, 0, n-1, make_pair(it.y, it.z), it.x);
      // cout<<i<<" "<<it.x<<" "<<it.y<<"\n";
    }
    if(st.st[1].first==-1) finalHeight[i]=0;
    else finalHeight[i]=st.st[1].second;
  }
  return;
}

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