oj.uz

Submission #938838

# Submission time Handle Problem Language Result Execution time Memory
938838 2024-03-05T15:54:13 Z codefox Wall (IOI14_wall) C++14
100 / 100
 594 ms 70228 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] = bmx[curr];
    }
    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] = bmx[curr];
    }
    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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33116 KB Output is correct
2 Correct 21 ms 33116 KB Output is correct
3 Correct 21 ms 33116 KB Output is correct
4 Correct 26 ms 33368 KB Output is correct
5 Correct 24 ms 33372 KB Output is correct
6 Correct 25 ms 33304 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33116 KB Output is correct
2 Correct 232 ms 41100 KB Output is correct
3 Correct 160 ms 36584 KB Output is correct
4 Correct 399 ms 41612 KB Output is correct
5 Correct 269 ms 52272 KB Output is correct
6 Correct 271 ms 50608 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33068 KB Output is correct
2 Correct 20 ms 33368 KB Output is correct
3 Correct 21 ms 33116 KB Output is correct
4 Correct 26 ms 33480 KB Output is correct
5 Correct 24 ms 33476 KB Output is correct
6 Correct 24 ms 33484 KB Output is correct
7 Correct 17 ms 33116 KB Output is correct
8 Correct 238 ms 47164 KB Output is correct
9 Correct 160 ms 40228 KB Output is correct
10 Correct 396 ms 51220 KB Output is correct
11 Correct 311 ms 52280 KB Output is correct
12 Correct 267 ms 50768 KB Output is correct
13 Correct 19 ms 33112 KB Output is correct
14 Correct 236 ms 46904 KB Output is correct
15 Correct 51 ms 34384 KB Output is correct
16 Correct 552 ms 51484 KB Output is correct
17 Correct 320 ms 50900 KB Output is correct
18 Correct 295 ms 50928 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33116 KB Output is correct
2 Correct 20 ms 33336 KB Output is correct
3 Correct 21 ms 33112 KB Output is correct
4 Correct 26 ms 33372 KB Output is correct
5 Correct 23 ms 33484 KB Output is correct
6 Correct 25 ms 33304 KB Output is correct
7 Correct 18 ms 33116 KB Output is correct
8 Correct 258 ms 46904 KB Output is correct
9 Correct 161 ms 40352 KB Output is correct
10 Correct 401 ms 51344 KB Output is correct
11 Correct 273 ms 52280 KB Output is correct
12 Correct 287 ms 50880 KB Output is correct
13 Correct 19 ms 33288 KB Output is correct
14 Correct 235 ms 46676 KB Output is correct
15 Correct 51 ms 34384 KB Output is correct
16 Correct 556 ms 51536 KB Output is correct
17 Correct 283 ms 50772 KB Output is correct
18 Correct 285 ms 50772 KB Output is correct
19 Correct 536 ms 69636 KB Output is correct
20 Correct 540 ms 67408 KB Output is correct
21 Correct 586 ms 69464 KB Output is correct
22 Correct 542 ms 67008 KB Output is correct
23 Correct 539 ms 67424 KB Output is correct
24 Correct 533 ms 67160 KB Output is correct
25 Correct 594 ms 67152 KB Output is correct
26 Correct 544 ms 69712 KB Output is correct
27 Correct 539 ms 70228 KB Output is correct
28 Correct 538 ms 67248 KB Output is correct
29 Correct 551 ms 67164 KB Output is correct
30 Correct 541 ms 67044 KB Output is correct