oj.uz

Submission #202799

# Submission time Handle Problem Language Result Execution time Memory
202799 2020-02-17T23:51:22 Z DavidDamian Wall (IOI14_wall) C++11
0 / 100
 5 ms 376 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
unsigned short 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;
    unsigned short a,b;
} lazy[6000005];
#define inf 100001
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=0;
    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=0;
        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);
    }
}

Compilation message

wall.cpp: In function 'void propagate(int, int, int)':
wall.cpp:22:13: warning: large integer implicitly truncated to unsigned type [-Woverflow]
 #define inf 100001
             ^
wall.cpp:51:15: note: in expansion of macro 'inf'
     lazy[i].b=inf;
               ^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:22:13: warning: large integer implicitly truncated to unsigned type [-Woverflow]
 #define inf 100001
             ^
wall.cpp:90:19: note: in expansion of macro 'inf'
         lazy[i].b=inf;
                   ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -