oj.uz

Submission #972857

# Submission time Handle Problem Language Result Execution time Memory
972857 2024-05-01T09:09:33 Z sleepntsheep Wall (IOI14_wall) C
100 / 100
 711 ms 102480 KB 
#include "wall.h"

#define MAX_N 4000002

int lo(int a,int b){return a>b?b:a;}
int hi(int a,int b){return a<b?b:a;}

int min[MAX_N<<2], max[MAX_N<<2];

void apply(int v,int kl,int kh)
{
    min[v]=hi(kh,lo(min[v],kl));
    max[v]=hi(kh,lo(max[v],kl));
}

void push(int v,int l,int r)
{
    apply(v<<1,min[v],max[v]);
    apply(v<<1|1,min[v],max[v]);
    if(l!=r) min[v]=1e9,max[v]=-1e9;
}

void upd(int v,int l,int r,int x,int y,int kl,int kh)
{
    push(v,l,r);
    if(r<x||y<l)return;
    if(x<=l&&r<=y){apply(v,kl,kh);return;}
    upd(v<<1,l,l+(r-l)/2,x,y,kl,kh),upd(v<<1|1,l+(r-l)/2+1,r,x,y,kl,kh);
}

void build(int v,int l,int r)
{
    if(l==r)min[v]=max[v]=0;
    else build(v<<1,l,l+(r-l)/2),build(v<<1|1,l+(r-l)/2+1,r);
}

void ans(int v,int l,int r,int *o)
{
    push(v,l,r);
    if(l==r){o[l]=min[v];return;}
    ans(v<<1,l,l+(r-l)/2,o),ans(v<<1|1,l+(r-l)/2+1,r,o);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1,0,n-1);
    for(int i=0;i<k;++i) upd(1,0,n-1,left[i],right[i],op[i]==1?1e9:height[i],op[i]==2?-1e9:height[i]);
    ans(1,0,n-1,finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 5 ms 4896 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 99 ms 10264 KB Output is correct
3 Correct 140 ms 8352 KB Output is correct
4 Correct 392 ms 13044 KB Output is correct
5 Correct 253 ms 13652 KB Output is correct
6 Correct 244 ms 13332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct
7 Correct 0 ms 2472 KB Output is correct
8 Correct 101 ms 10304 KB Output is correct
9 Correct 140 ms 8276 KB Output is correct
10 Correct 457 ms 12960 KB Output is correct
11 Correct 242 ms 13396 KB Output is correct
12 Correct 249 ms 13580 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 104 ms 10132 KB Output is correct
15 Correct 23 ms 5468 KB Output is correct
16 Correct 402 ms 13220 KB Output is correct
17 Correct 254 ms 13140 KB Output is correct
18 Correct 246 ms 13136 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 5 ms 4904 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 4 ms 4836 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 99 ms 10480 KB Output is correct
9 Correct 142 ms 8344 KB Output is correct
10 Correct 397 ms 12884 KB Output is correct
11 Correct 271 ms 13392 KB Output is correct
12 Correct 250 ms 13308 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 104 ms 10140 KB Output is correct
15 Correct 23 ms 5596 KB Output is correct
16 Correct 453 ms 13212 KB Output is correct
17 Correct 271 ms 13144 KB Output is correct
18 Correct 266 ms 13216 KB Output is correct
19 Correct 589 ms 91964 KB Output is correct
20 Correct 656 ms 99916 KB Output is correct
21 Correct 711 ms 102480 KB Output is correct
22 Correct 587 ms 99764 KB Output is correct
23 Correct 579 ms 99924 KB Output is correct
24 Correct 571 ms 100176 KB Output is correct
25 Correct 686 ms 99812 KB Output is correct
26 Correct 611 ms 102404 KB Output is correct
27 Correct 607 ms 102372 KB Output is correct
28 Correct 626 ms 99872 KB Output is correct
29 Correct 602 ms 99956 KB Output is correct
30 Correct 618 ms 99812 KB Output is correct