oj.uz

Submission #202802

# Submission time Handle Problem Language Result Execution time Memory
202802 2020-02-17T23:54:22 Z DavidDamian Wall (IOI14_wall) C++11
100 / 100
 1166 ms 102520 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segm_tree[6000000];
int leftNode(int i)
{
    return i*2;
}
int rightNode(int i)
{
    return i*2+1;
}
void recompute(int i)
{
    segm_tree[i]=max(segm_tree[leftNode(i)],segm_tree[rightNode(i)]);
}
struct bound
{
    int on;
    int a,b;
} lazy[6000005];
#define inf 1000000
void combine(int cur,int past)
{
    if(lazy[cur].on==0){
        lazy[cur]=lazy[past];
        return;
    }
    int x=lazy[past].a;
    if(x>lazy[cur].a)
        lazy[cur].a=x;
    if(x>lazy[cur].b)
        lazy[cur].b=x;
    x=lazy[past].b;
    if(x<lazy[cur].a)
        lazy[cur].a=x;
    if(x<lazy[cur].b)
        lazy[cur].b=x;
}
void propagate(int i,int L,int R)
{
    if(lazy[i].on==0) return;
    segm_tree[i]=max(segm_tree[i],lazy[i].a);
    segm_tree[i]=min(segm_tree[i],lazy[i].b);
    if(L<R){
        combine(leftNode(i),i);
        combine(rightNode(i),i);
    }
    lazy[i].on=0;
    lazy[i].a=-inf;
    lazy[i].b=inf;
}
void update(int i,int L,int R,int x,int y,int type,int h)
{
    propagate(i,L,R);
    if(x<=L && R<=y){
        if(type==1) lazy[i].a=h,lazy[i].b=inf;
        else lazy[i].a=-inf,lazy[i].b=h;
        lazy[i].on=1;
    }
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            update(leftNode(i),L,mid,x,y,type,h);
        if(mid+1<=y)
            update(rightNode(i),mid+1,R,x,y,type,h);
        propagate(leftNode(i),L,mid);
        propagate(rightNode(i),mid+1,R);
        recompute(i);
    }
}
int query(int i,int L,int R,int x)
{
    propagate(i,L,R);
    if(L==R){
        return segm_tree[i];
    }
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            return query(leftNode(i),L,mid,x);
        else
            return query(rightNode(i),mid+1,R,x);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0;i<k;i++){
        update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=query(1,1,n,i+1);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 15 ms 1016 KB Output is correct
5 Correct 11 ms 1020 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 183 ms 8184 KB Output is correct
3 Correct 371 ms 4728 KB Output is correct
4 Correct 1143 ms 12940 KB Output is correct
5 Correct 329 ms 13432 KB Output is correct
6 Correct 322 ms 13560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 15 ms 1016 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 11 ms 1016 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 186 ms 8184 KB Output is correct
9 Correct 377 ms 4788 KB Output is correct
10 Correct 1131 ms 12888 KB Output is correct
11 Correct 332 ms 13432 KB Output is correct
12 Correct 327 ms 13308 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 185 ms 8184 KB Output is correct
15 Correct 65 ms 2040 KB Output is correct
16 Correct 1166 ms 13244 KB Output is correct
17 Correct 327 ms 13176 KB Output is correct
18 Correct 318 ms 13176 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 9 ms 424 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 15 ms 1016 KB Output is correct
5 Correct 11 ms 1016 KB Output is correct
6 Correct 12 ms 1016 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 181 ms 8184 KB Output is correct
9 Correct 370 ms 4728 KB Output is correct
10 Correct 1130 ms 12920 KB Output is correct
11 Correct 347 ms 13432 KB Output is correct
12 Correct 324 ms 13432 KB Output is correct
13 Correct 5 ms 372 KB Output is correct
14 Correct 183 ms 8184 KB Output is correct
15 Correct 66 ms 2040 KB Output is correct
16 Correct 1164 ms 13176 KB Output is correct
17 Correct 339 ms 13176 KB Output is correct
18 Correct 335 ms 13096 KB Output is correct
19 Correct 1030 ms 92024 KB Output is correct
20 Correct 1026 ms 100088 KB Output is correct
21 Correct 1026 ms 102520 KB Output is correct
22 Correct 1059 ms 99904 KB Output is correct
23 Correct 1058 ms 99960 KB Output is correct
24 Correct 1044 ms 100092 KB Output is correct
25 Correct 1056 ms 99948 KB Output is correct
26 Correct 1046 ms 102400 KB Output is correct
27 Correct 1022 ms 102520 KB Output is correct
28 Correct 1012 ms 100104 KB Output is correct
29 Correct 1030 ms 99960 KB Output is correct
30 Correct 1031 ms 99836 KB Output is correct