oj.uz

Submission #744646

# Submission time Handle Problem Language Result Execution time Memory
744646 2023-05-18T22:07:03 Z angels Wall (IOI14_wall) C++14
100 / 100
 613 ms 69520 KB 
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#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;
        cin>>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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33080 KB Output is correct
2 Correct 28 ms 33172 KB Output is correct
3 Correct 28 ms 33088 KB Output is correct
4 Correct 31 ms 33356 KB Output is correct
5 Correct 31 ms 33336 KB Output is correct
6 Correct 30 ms 33268 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33100 KB Output is correct
2 Correct 298 ms 46716 KB Output is correct
3 Correct 184 ms 40424 KB Output is correct
4 Correct 483 ms 49980 KB Output is correct
5 Correct 308 ms 52132 KB Output is correct
6 Correct 292 ms 50636 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33100 KB Output is correct
2 Correct 28 ms 33224 KB Output is correct
3 Correct 29 ms 33120 KB Output is correct
4 Correct 31 ms 33308 KB Output is correct
5 Correct 32 ms 33356 KB Output is correct
6 Correct 30 ms 33352 KB Output is correct
7 Correct 28 ms 33088 KB Output is correct
8 Correct 327 ms 46712 KB Output is correct
9 Correct 196 ms 40176 KB Output is correct
10 Correct 506 ms 50020 KB Output is correct
11 Correct 318 ms 52104 KB Output is correct
12 Correct 313 ms 50536 KB Output is correct
13 Correct 26 ms 33076 KB Output is correct
14 Correct 306 ms 46780 KB Output is correct
15 Correct 56 ms 34252 KB Output is correct
16 Correct 479 ms 51552 KB Output is correct
17 Correct 325 ms 50840 KB Output is correct
18 Correct 319 ms 50728 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33108 KB Output is correct
2 Correct 29 ms 33236 KB Output is correct
3 Correct 26 ms 33184 KB Output is correct
4 Correct 30 ms 33352 KB Output is correct
5 Correct 30 ms 33308 KB Output is correct
6 Correct 28 ms 33356 KB Output is correct
7 Correct 25 ms 33100 KB Output is correct
8 Correct 297 ms 46716 KB Output is correct
9 Correct 196 ms 40176 KB Output is correct
10 Correct 485 ms 49972 KB Output is correct
11 Correct 355 ms 52172 KB Output is correct
12 Correct 299 ms 50532 KB Output is correct
13 Correct 33 ms 33100 KB Output is correct
14 Correct 294 ms 46756 KB Output is correct
15 Correct 55 ms 34284 KB Output is correct
16 Correct 489 ms 51352 KB Output is correct
17 Correct 364 ms 50892 KB Output is correct
18 Correct 296 ms 50856 KB Output is correct
19 Correct 613 ms 69436 KB Output is correct
20 Correct 603 ms 67064 KB Output is correct
21 Correct 601 ms 69520 KB Output is correct
22 Correct 612 ms 67080 KB Output is correct
23 Correct 607 ms 67004 KB Output is correct
24 Correct 610 ms 66968 KB Output is correct
25 Correct 594 ms 66936 KB Output is correct
26 Correct 602 ms 69476 KB Output is correct
27 Correct 586 ms 69516 KB Output is correct
28 Correct 610 ms 66996 KB Output is correct
29 Correct 610 ms 67044 KB Output is correct
30 Correct 588 ms 67024 KB Output is correct