oj.uz

Submission #378078

# Submission time Handle Problem Language Result Execution time Memory
378078 2021-03-16T00:15:25 Z ScarletS Wall (IOI14_wall) C++17
100 / 100
 824 ms 69740 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);
}

/**
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin>>n>>k;
    int op[k],l[k],r[k],h[k],a[n];
    for (int i=0;i<k;++i)
        cin>>op[i];
    for (int i=0;i<k;++i)
        cin>>l[i]>>r[i];
    for (int i=0;i<k;++i)
        cin>>h[i];
    buildWall(n,k,op,l,r,h,a);
    for (int i=0;i<n;++i)
        cout<<a[i]<<" ";
    return 0;
}
**/

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 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 156 ms 10732 KB Output is correct
3 Correct 182 ms 7464 KB Output is correct
4 Correct 527 ms 12652 KB Output is correct
5 Correct 339 ms 13036 KB Output is correct
6 Correct 334 ms 13548 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 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 161 ms 13208 KB Output is correct
9 Correct 199 ms 8044 KB Output is correct
10 Correct 534 ms 14828 KB Output is correct
11 Correct 347 ms 15340 KB Output is correct
12 Correct 336 ms 15724 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 13164 KB Output is correct
15 Correct 30 ms 2028 KB Output is correct
16 Correct 516 ms 20716 KB Output is correct
17 Correct 347 ms 20204 KB Output is correct
18 Correct 345 ms 20076 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 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 900 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 162 ms 13164 KB Output is correct
9 Correct 181 ms 8044 KB Output is correct
10 Correct 505 ms 14828 KB Output is correct
11 Correct 344 ms 15340 KB Output is correct
12 Correct 333 ms 15596 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 13292 KB Output is correct
15 Correct 30 ms 2028 KB Output is correct
16 Correct 512 ms 20716 KB Output is correct
17 Correct 341 ms 20076 KB Output is correct
18 Correct 345 ms 20076 KB Output is correct
19 Correct 816 ms 69612 KB Output is correct
20 Correct 810 ms 66992 KB Output is correct
21 Correct 814 ms 69568 KB Output is correct
22 Correct 805 ms 67180 KB Output is correct
23 Correct 811 ms 67180 KB Output is correct
24 Correct 807 ms 67308 KB Output is correct
25 Correct 824 ms 67152 KB Output is correct
26 Correct 818 ms 69612 KB Output is correct
27 Correct 820 ms 69740 KB Output is correct
28 Correct 805 ms 67052 KB Output is correct
29 Correct 811 ms 67108 KB Output is correct
30 Correct 806 ms 67164 KB Output is correct