oj.uz

Submission #202797

# Submission time Handle Problem Language Result Execution time Memory
202797 2020-02-17T23:48:16 Z DavidDamian Wall (IOI14_wall) C++11
61 / 100
 1169 ms 185468 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segm_tree[5000000];
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[5000005];
#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 380 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 7 ms 388 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 5 ms 376 KB Output is correct
2 Correct 179 ms 9592 KB Output is correct
3 Correct 371 ms 6264 KB Output is correct
4 Correct 1150 ms 15736 KB Output is correct
5 Correct 334 ms 17112 KB Output is correct
6 Correct 320 ms 16248 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 504 KB Output is correct
3 Correct 8 ms 456 KB Output is correct
4 Correct 16 ms 1272 KB Output is correct
5 Correct 11 ms 1144 KB Output is correct
6 Correct 11 ms 1176 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 179 ms 9492 KB Output is correct
9 Correct 372 ms 6220 KB Output is correct
10 Correct 1134 ms 15864 KB Output is correct
11 Correct 335 ms 16432 KB Output is correct
12 Correct 320 ms 16248 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 183 ms 9592 KB Output is correct
15 Correct 64 ms 2552 KB Output is correct
16 Correct 1153 ms 16376 KB Output is correct
17 Correct 339 ms 23744 KB Output is correct
18 Correct 334 ms 23800 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 7 ms 504 KB Output is correct
3 Correct 7 ms 380 KB Output is correct
4 Correct 16 ms 1148 KB Output is correct
5 Correct 11 ms 1148 KB Output is correct
6 Correct 11 ms 1144 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 189 ms 9784 KB Output is correct
9 Correct 372 ms 6264 KB Output is correct
10 Correct 1100 ms 15736 KB Output is correct
11 Correct 336 ms 17144 KB Output is correct
12 Correct 328 ms 16404 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 184 ms 9592 KB Output is correct
15 Correct 66 ms 2552 KB Output is correct
16 Correct 1169 ms 16320 KB Output is correct
17 Correct 335 ms 23800 KB Output is correct
18 Correct 334 ms 23804 KB Output is correct
19 Runtime error 355 ms 185468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -