Submission #1245058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245058		nekolie	Wall (IOI14_wall)	C++20	100 / 100	1435 ms	223932 KiB

wall

// Fluixarata or Cyngulini?
// That is the question...
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int baza1 = (1<<21), baza2 = (1<<19), inf = (1<<30);
int segs[baza2][4], odp[baza1], d[2*baza2][2];
vector<int> ind[2*baza1];
void push(int l, int r, int i) {
    l += baza1-1, r += baza1+1;
    while (l/2 != r/2) {
        if (l%2 == 0)
            ind[l+1].push_back(i);
        if (r%2 == 1)
            ind[r-1].push_back(i);
        l /= 2, r /= 2;
    }
}
void akt(int i) {
    i = (i+baza2)/2;
    while (i > 0)
        d[i][0] = min(d[2*i][0],d[2*i+1][0]), d[i][1] = max(d[2*i][1],d[2*i+1][1]), i /= 2;
}
int val() {
    int v = 1, mini = inf, maks = -inf;
    while (v < baza2) {
        if (min(mini,d[2*v+1][0]) >= max(maks,d[2*v+1][1]))
            mini = min(mini,d[2*v+1][0]), maks = max(maks,d[2*v+1][1]), v = 2*v;
        else
            v = 2*v+1;
    }
    if (maks == -inf && v == baza2)
        return 0;
    return ((segs[v-baza2][3] <= maks) ? maks : mini);
}
void dfs(int v) {
    for (int i : ind[v])
        d[i+baza2][2-segs[i][2]] = segs[i][3], akt(i);
    if (v < baza1)
        dfs(2*v), dfs(2*v+1);
    else
        odp[v-baza1] = val();
    for (int i : ind[v])
        d[i+baza2][0] = inf, d[i+baza2][1] = -inf, akt(i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 1; i < 2*baza2; i++)
        d[i][0] = inf, d[i][1] = -inf;
    for (int i = 0; i < k; i++)
        segs[i+1][0] = left[i], segs[i+1][1] = right[i], segs[i+1][2] = op[i], segs[i+1][3] = height[i], push(left[i],right[i],i+1);
    dfs(1);
    for (int i = 0; i < n; i++)
        finalHeight[i] = odp[i];
}

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