oj.uz

Submission #938824

# Submission time Handle Problem Language Result Execution time Memory
938824 2024-03-05T15:38:40 Z codefox Wall (IOI14_wall) C++14
0 / 100
 234 ms 40872 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]) 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;
    }
    mn = max(bmn[curr], mn);
    mx = min(bmx[curr], mx);

    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]) bmn[curr] = mn;
    }
    if (mn > bmn[curr])
    {
        bmn[curr] = mn;
        if(bmx[curr]<bmn[curr]) bmx[curr] = bmn[curr];
    }
    mn = max(bmn[curr], mn);
    mx = min(bmx[curr], mx);

    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 = N; i < N+n; i++)
    {
        finalHeight[i-N] = bmn[i];
    }
    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 20 ms 33112 KB Output is correct
2 Correct 19 ms 33116 KB Output is correct
3 Incorrect 21 ms 33112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33204 KB Output is correct
2 Correct 234 ms 40872 KB Output is correct
3 Incorrect 157 ms 36580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33248 KB Output is correct
2 Correct 19 ms 33116 KB Output is correct
3 Incorrect 18 ms 33116 KB Output isn't correct
4 Halted 0 ms 0 KB -