oj.uz

답안 #744655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744655 2023-05-18T22:43:50 Z vjudge1 벽 (IOI14_wall) C++17
100 / 100
 618 ms 60260 KB 
#include <bits/stdc++.h>
 
using namespace std;

int RIGHT=2097152;
int d[5000000], g[5000000];
int N, K;
void update(int l, int r, int p, int h, int n, int a, int b)
{
    if(b<l || r<a) 
        return;
    if(l<=a && b<=r)
    {
        if(p==1)        //add
        {
            d[n]=max(d[n], h);
            g[n]=max(g[n], h);
        }
        if(p==2)        //remove
        {
            d[n]=min(d[n], h);
            g[n]=min(g[n], h);
        }
        return;
    }
    d[2*n]=max(min(d[2*n], d[n]), g[n]);
    g[2*n]=min(max(g[2*n], g[n]), d[n]);
    d[2*n+1]=max(min(d[2*n+1], d[n]), g[n]);
    g[2*n+1]=min(max(g[2*n+1], g[n]), d[n]);
    d[n]=10000000;
    g[n]=0;
    int mid=(a+b)/2;
    update(l, r, p, h, 2*n, a, mid);
    update(l, r, p, h, 2*n+1, mid+1, b);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    N=n, K=k;
    for(int i=0; i<K; i++)
    {
        int p, l, r, h;
        p=op[i]; 
        l=left[i];
        r=right[i];
        h=height[i];
        update(l+1, r+1, p, h, 1, 1, RIGHT);
    }
    for(int i=1; i<=RIGHT-1; i++)
    {
        d[2*i]=max(min(d[2*i], d[i]), g[i]);
        g[2*i]=min(max(g[2*i], g[i]), d[i]);
        d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
        g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
    }
    for(int i=RIGHT; i<=RIGHT+N-1; i++)
    {
        finalHeight[i-RIGHT]=min(d[i],g[i]);
    }
}
/*int main()
{
    cin>>N>>K;
    for(int i=1; i<=K; i++)
    {
        int p, l, r, h;
        cin>>p>>l>>r>>h;
        update(l+1, r+1, p, h, 1, 1, RIGHT);
    }
    for(int i=1; i<=RIGHT-1; i++)
    {
        d[2*i]=max(min(d[2*i], d[i]), g[i]);
        g[2*i]=min(max(g[2*i], g[i]), d[i]);
        d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
        g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
    }
    for(int i=RIGHT; i<=RIGHT+N-1; i++)
        cout<<min(d[i],g[i])<<"\n";
}*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33100 KB Output is correct
2 Correct 29 ms 33296 KB Output is correct
3 Correct 27 ms 33100 KB Output is correct
4 Correct 37 ms 33376 KB Output is correct
5 Correct 32 ms 33388 KB Output is correct
6 Correct 29 ms 33364 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 33060 KB Output is correct
2 Correct 279 ms 41840 KB Output is correct
3 Correct 179 ms 37436 KB Output is correct
4 Correct 520 ms 43416 KB Output is correct
5 Correct 293 ms 43416 KB Output is correct
6 Correct 290 ms 43360 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 33080 KB Output is correct
2 Correct 30 ms 33168 KB Output is correct
3 Correct 28 ms 33108 KB Output is correct
4 Correct 32 ms 33368 KB Output is correct
5 Correct 31 ms 33284 KB Output is correct
6 Correct 32 ms 33360 KB Output is correct
7 Correct 26 ms 33100 KB Output is correct
8 Correct 267 ms 41844 KB Output is correct
9 Correct 177 ms 37296 KB Output is correct
10 Correct 483 ms 43372 KB Output is correct
11 Correct 292 ms 43480 KB Output is correct
12 Correct 295 ms 43388 KB Output is correct
13 Correct 27 ms 33080 KB Output is correct
14 Correct 282 ms 42392 KB Output is correct
15 Correct 52 ms 34252 KB Output is correct
16 Correct 478 ms 43240 KB Output is correct
17 Correct 290 ms 43252 KB Output is correct
18 Correct 278 ms 43220 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 33108 KB Output is correct
2 Correct 30 ms 33232 KB Output is correct
3 Correct 29 ms 33128 KB Output is correct
4 Correct 30 ms 33364 KB Output is correct
5 Correct 32 ms 33380 KB Output is correct
6 Correct 31 ms 33344 KB Output is correct
7 Correct 26 ms 33108 KB Output is correct
8 Correct 267 ms 41924 KB Output is correct
9 Correct 189 ms 37372 KB Output is correct
10 Correct 483 ms 43384 KB Output is correct
11 Correct 298 ms 43364 KB Output is correct
12 Correct 284 ms 43396 KB Output is correct
13 Correct 26 ms 33016 KB Output is correct
14 Correct 273 ms 42388 KB Output is correct
15 Correct 51 ms 34240 KB Output is correct
16 Correct 492 ms 43232 KB Output is correct
17 Correct 306 ms 43260 KB Output is correct
18 Correct 311 ms 43184 KB Output is correct
19 Correct 571 ms 60176 KB Output is correct
20 Correct 572 ms 57644 KB Output is correct
21 Correct 569 ms 60260 KB Output is correct
22 Correct 589 ms 57720 KB Output is correct
23 Correct 591 ms 57720 KB Output is correct
24 Correct 588 ms 57708 KB Output is correct
25 Correct 568 ms 57552 KB Output is correct
26 Correct 592 ms 60020 KB Output is correct
27 Correct 586 ms 59972 KB Output is correct
28 Correct 579 ms 57492 KB Output is correct
29 Correct 572 ms 57468 KB Output is correct
30 Correct 618 ms 57544 KB Output is correct