Submission #1123069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123069		SalihSahin	Wall (IOI14_wall)	C++20	100 / 100	535 ms	106768 KiB

wall

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "wall.h"

const int MX = 1e5 + 5;

pair<int, int> merge(pair<int, int> &a, pair<int, int> &b){
    if(min(a.second, b.second) < max(a.first, b.first)){ // kesisme yok
        if(b.first > a.second) return {b.first, b.first};
        else return {b.second, b.second};
    }
    else{
        return {max(a.first, b.first), min(a.second, b.second)};
    }
}

struct SEGT{
    vector<pair<int, int> > tree;

    void init(int n){
        tree.assign(4*n, {0, MX});
    }


    void update(int ind, int l, int r, int pos, pair<int, int> val){
        if(l == r){
            tree[ind] = val;
        }
        else{
            int m = (l + r)/2;

            if(pos <= m) update(ind*2, l, m, pos, val);
            else update(ind*2+1, m+1, r, pos, val);

            tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  vector<array<int, 4> > updates[n+1];
  for(int i = 0; i < k; i++){
    updates[left[i]].pb({i+1, height[i], op[i], 1});
    updates[right[i] + 1].pb({i+1, height[i], op[i], -1});
  }

  SEGT seg;
  seg.init(k);

  for(int i = 0; i < n; i++){
    for(auto itr: updates[i]){
        pair<int, int> val = {0, MX};
        if(itr[3] == -1){
            seg.update(1, 1, k, itr[0], val);
        }
        else{
            if(itr[2] == 1) val = {itr[1], MX};
            else val = {0, itr[1]};
            seg.update(1, 1, k, itr[0], val);
        }
    }

    finalHeight[i] = seg.tree[1].first;
  }

  return;
}

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