oj.uz

Submission #972856

# Submission time Handle Problem Language Result Execution time Memory
972856 2024-05-01T09:08:43 Z sleepntsheep Wall (IOI14_wall) C
61 / 100
 422 ms 85144 KB 
#include "wall.h"

#define MAX_N 2000002

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 1 ms 2396 KB Output is correct
2 Correct 2 ms 2548 KB Output is correct
3 Correct 1 ms 2520 KB Output is correct
4 Correct 5 ms 2936 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 4 ms 2908 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 108 ms 10120 KB Output is correct
3 Correct 141 ms 6304 KB Output is correct
4 Correct 406 ms 14932 KB Output is correct
5 Correct 251 ms 25588 KB Output is correct
6 Correct 246 ms 24048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 2908 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 107 ms 16068 KB Output is correct
9 Correct 145 ms 10068 KB Output is correct
10 Correct 408 ms 24656 KB Output is correct
11 Correct 250 ms 25428 KB Output is correct
12 Correct 253 ms 24076 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 104 ms 15884 KB Output is correct
15 Correct 22 ms 4096 KB Output is correct
16 Correct 398 ms 24784 KB Output is correct
17 Correct 268 ms 24204 KB Output is correct
18 Correct 249 ms 24204 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 2908 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 102 ms 15952 KB Output is correct
9 Correct 156 ms 10076 KB Output is correct
10 Correct 422 ms 24400 KB Output is correct
11 Correct 250 ms 25588 KB Output is correct
12 Correct 244 ms 24056 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 104 ms 15956 KB Output is correct
15 Correct 23 ms 4084 KB Output is correct
16 Correct 412 ms 24780 KB Output is correct
17 Correct 281 ms 24148 KB Output is correct
18 Correct 255 ms 24400 KB Output is correct
19 Runtime error 148 ms 85144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -