oj.uz

Submission #938834

# Submission time Handle Problem Language Result Execution time Memory
938834 2024-03-05T15:48:47 Z codefox Wall (IOI14_wall) C++14
0 / 100
 470 ms 46732 KB 
#include<bits/stdc++.h>
#include<wall.h>

using namespace std;

int N = 1<<21;
vector<int> bmn(2*N, 0);
vector<int> bmx(2*N, 0);
int ox, on;

void update(int curr, int l, int r, int ll, int rr, int mx, int mn)
{
    if (mx < bmx[curr])
    {
        bmx[curr] = mx;
        if (bmx[curr]<bmn[curr] && mn <= bmn[curr]) bmn[curr] = mn;
    }
    if (mn > bmn[curr])
    {
        bmn[curr] = mn;
        if(bmx[curr]<bmn[curr]) bmx[curr] = bmn[curr];
    }

    if (l >= rr || r <= ll) return;
    if (l >= ll && r <= rr) 
    {
        if (ox != -1) 
        {
            if (bmn[curr]>ox) bmn[curr] = ox;
            bmx[curr] = min(ox, bmx[curr]);
        }
        else
        {
            if (bmx[curr]<on) bmx[curr] = on;  
            bmn[curr] = max(bmn[curr], on); 
        }
        return;
    }
    
    if (mx > bmx[curr])
    {
        mx = bmx[curr];
        if (mx < mn && mn >= bmn[curr]) mn = mx;
    }
    if (mn < bmn[curr])
    {
        mn = bmn[curr];
        if (mx < mn) mx = mn;
    }

    int m = (r+l)/2;
    update(curr*2, l, m, ll, rr, mx, mn);
    update(curr*2+1, m, r, ll, rr, mx, mn);
    bmn[curr] = min(bmn[curr*2], bmn[curr*2+1]);
    bmx[curr] = max(bmx[curr*2], bmx[curr*2+1]);
}

void dfs(int curr, int mx, int mn)
{
    if (mx < bmx[curr])
    {
        bmx[curr] = mx;
        if (bmx[curr]<bmn[curr] && mn <= bmn[curr]) bmn[curr] = mn;
    }
    if (mn > bmn[curr])
    {
        bmn[curr] = mn;
        if(bmx[curr]<bmn[curr]) bmx[curr] = bmn[curr];
    }

    if (mx > bmx[curr])
    {
        mx = bmx[curr];
        if (mx < mn && mn >= bmn[curr]) mn = mx;
    }
    if (mn < bmn[curr])
    {
        mn = bmn[curr];
        if (mx < mn) mx = mn;
    }

    if (curr >= N) return;

    dfs(curr*2, mx, mn);
    dfs(curr*2+1, mx, mn);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; i++)
    {
        on = -1;
        ox = -1;
        if (op[i]==1) on = height[i];
        else ox = height[i];
        update(1, 0, N, left[i], right[i]+1, 1e9, 0);
    }
    dfs(1, 1e9, 0);
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = bmx[i+N];
    }
    return;
}


/*
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;

    int op[k];
    int left[k];
    int right[k];
    int height[k];
    int finalHeight[n];

    for (int i =0; i < k; i++)
    {
        cin >> op[i];
        cin >> left[i];
        cin >> right[i];
        cin >> height[i];
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int ele:finalHeight) cout << ele << " ";

    return 0;
}
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33120 KB Output is correct
2 Correct 26 ms 33372 KB Output is correct
3 Incorrect 30 ms 33364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33116 KB Output is correct
2 Correct 248 ms 44168 KB Output is correct
3 Correct 171 ms 38020 KB Output is correct
4 Incorrect 470 ms 46732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33116 KB Output is correct
2 Correct 25 ms 33416 KB Output is correct
3 Incorrect 24 ms 33112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33116 KB Output is correct
2 Correct 26 ms 33372 KB Output is correct
3 Incorrect 23 ms 33116 KB Output isn't correct
4 Halted 0 ms 0 KB -