oj.uz

Submission #378079

# Submission time Handle Problem Language Result Execution time Memory
378079 2021-03-16T00:17:27 Z ScarletS Wall (IOI14_wall) C++17
100 / 100
 847 ms 59244 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e5, mn = 2e6+7;
int seg[mn<<2][2];

void passDown(int i)
{
    for (int j=i*2+1;j<i*2+3;++j)
    {
        seg[j][0]=max(seg[j][0],seg[i][0]);
        seg[j][1]=max(seg[j][0],seg[j][1]);
        seg[j][1]=min(seg[j][1],seg[i][1]);
        seg[j][0]=min(seg[j][0],seg[j][1]);
    }
    seg[i][0]=0;
    seg[i][1]=INF;
}

void update(int i, int l, int r, int op, int L, int R, int h)
{
    if (R<l||r<L)
        return;
    if (L<=l&&r<=R)
    {
        if (op==1)
        {
            seg[i][0]=max(seg[i][0],h);
            seg[i][1]=max(seg[i][1],h);
        }
        else
        {
            seg[i][0]=min(seg[i][0],h);
            seg[i][1]=min(seg[i][1],h);
        }
        return;
    }
    passDown(i);
    update(i*2+1,l,l+(r-l)/2,op,L,R,h);
    update(i*2+2,l+(r-l)/2+1,r,op,L,R,h);
}

void calc(int i, int l, int r, int ans[])
{
    if (l==r)
    {
        ans[l]=seg[i][0];
        return;
    }
    passDown(i);
    calc(i*2+1,l,l+(r-l)/2,ans);
    calc(i*2+2,l+(r-l)/2+1,r,ans);
}

void buildWall(int n, int k, int op[], int l[], int r[],
int h[], int ans[])
{
    for (int i=0;i<k;++i)
        update(0,0,n-1,op[i],l[i],r[i],h[i]);
    calc(0,0,n-1,ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 7 ms 748 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 157 ms 8300 KB Output is correct
3 Correct 181 ms 4332 KB Output is correct
4 Correct 515 ms 10844 KB Output is correct
5 Correct 339 ms 11404 KB Output is correct
6 Correct 331 ms 11372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 6 ms 748 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 170 ms 8172 KB Output is correct
9 Correct 180 ms 4204 KB Output is correct
10 Correct 522 ms 10860 KB Output is correct
11 Correct 339 ms 11372 KB Output is correct
12 Correct 340 ms 11484 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 162 ms 8172 KB Output is correct
15 Correct 32 ms 1516 KB Output is correct
16 Correct 565 ms 11164 KB Output is correct
17 Correct 340 ms 11116 KB Output is correct
18 Correct 336 ms 11116 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 158 ms 8172 KB Output is correct
9 Correct 179 ms 4204 KB Output is correct
10 Correct 520 ms 10860 KB Output is correct
11 Correct 343 ms 11500 KB Output is correct
12 Correct 332 ms 11372 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 160 ms 8172 KB Output is correct
15 Correct 30 ms 1516 KB Output is correct
16 Correct 511 ms 11116 KB Output is correct
17 Correct 342 ms 11228 KB Output is correct
18 Correct 411 ms 11004 KB Output is correct
19 Correct 814 ms 59232 KB Output is correct
20 Correct 804 ms 56684 KB Output is correct
21 Correct 806 ms 59116 KB Output is correct
22 Correct 847 ms 56684 KB Output is correct
23 Correct 802 ms 56684 KB Output is correct
24 Correct 815 ms 56640 KB Output is correct
25 Correct 810 ms 56556 KB Output is correct
26 Correct 806 ms 59244 KB Output is correct
27 Correct 819 ms 59116 KB Output is correct
28 Correct 821 ms 56624 KB Output is correct
29 Correct 802 ms 56684 KB Output is correct
30 Correct 800 ms 56684 KB Output is correct