oj.uz

Submission #202800

# Submission time Handle Problem Language Result Execution time Memory
202800 2020-02-17T23:51:57 Z DavidDamian Wall (IOI14_wall) C++11
61 / 100
 1152 ms 120440 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;
        else 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=1;i<=4*n;i++){
        lazy[i].on=0;
        lazy[i].a=-inf;
        lazy[i].b=inf;
    }
    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 7 ms 380 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 16 ms 1144 KB Output is correct
5 Correct 11 ms 1144 KB Output is correct
6 Correct 11 ms 1144 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 180 ms 8408 KB Output is correct
3 Correct 376 ms 4856 KB Output is correct
4 Correct 1130 ms 14472 KB Output is correct
5 Correct 333 ms 14968 KB Output is correct
6 Correct 320 ms 14968 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 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 15 ms 1144 KB Output is correct
5 Correct 12 ms 1144 KB Output is correct
6 Correct 11 ms 1144 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 173 ms 8184 KB Output is correct
9 Correct 384 ms 4856 KB Output is correct
10 Correct 1098 ms 14584 KB Output is correct
11 Correct 340 ms 15100 KB Output is correct
12 Correct 324 ms 15032 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 184 ms 8184 KB Output is correct
15 Correct 63 ms 2040 KB Output is correct
16 Correct 1141 ms 14840 KB Output is correct
17 Correct 331 ms 14840 KB Output is correct
18 Correct 324 ms 14904 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 15 ms 1144 KB Output is correct
5 Correct 11 ms 1144 KB Output is correct
6 Correct 11 ms 1144 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 178 ms 8184 KB Output is correct
9 Correct 374 ms 4856 KB Output is correct
10 Correct 1091 ms 14460 KB Output is correct
11 Correct 341 ms 15096 KB Output is correct
12 Correct 331 ms 15096 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 184 ms 8160 KB Output is correct
15 Correct 63 ms 2040 KB Output is correct
16 Correct 1152 ms 14840 KB Output is correct
17 Correct 347 ms 14840 KB Output is correct
18 Correct 320 ms 14716 KB Output is correct
19 Incorrect 1026 ms 120440 KB Output isn't correct
20 Halted 0 ms 0 KB -