Submission #202788

#	Time	Username	Problem	Language	Result	Execution time	Memory
202788		DavidDamian	Wall (IOI14_wall)	C++11	32 / 100	1316 ms	22464 KiB

wall

#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 ura
{
    int type;
    int var1;
    int var2;
} lazy[5000000];
#define add 1 //Add
#define rem 2 //Remove
#define change 3 //Change
#define bound 4 //Bound
ura Add(int i,int j)
{
    ura ret;
    int a,b,c;
    a=lazy[i].var1;
    b=lazy[j].var1;
    c=lazy[j].var2;
    if(lazy[j].type==add)
        ret={add,max(a,b),0};
    else if(lazy[j].type==rem){
        if(a>=b) ret={change,b,0};
        else ret={bound,a,b};
    }
    else if(lazy[j].type==change)
        ret={change,b,0};
    else if(lazy[j].type==bound){
        if(a<b) ret={bound,b,c};
        else if(a>c) ret={change,c,0};
        else ret={bound,a,c};
    }
    return ret;
}
ura Remove(int i,int j)
{
    ura ret;
    int a,b,c;
    a=lazy[i].var1;
    b=lazy[j].var1;
    c=lazy[j].var2;
    if(lazy[j].type==add){
        if(a<b) ret={change,b,0};
        else ret={bound,b,a};
    }
    else if(lazy[j].type==rem){
        ret={rem,min(a,b),0};
    }
    else if(lazy[j].type==change){
        ret={change,b,0};
    }
    else if(lazy[j].type==bound){
        if(a<b) ret={change,b,0};
        else if(a>c) ret={bound,b,c};
        else ret={bound,b,a};
    }
    return ret;
}
ura Change(int i,int j)
{
    ura ret;
    int a,b,c;
    a=lazy[i].var1;
    b=lazy[j].var1;
    c=lazy[j].var2;
    if(lazy[j].type==add){
        ret={change,max(a,b),0};
    }
    else if(lazy[j].type==rem){
        ret={change,min(a,b),0};
    }
    else if(lazy[j].type==change){
        ret={change,b,0};
    }
    else if(lazy[j].type==bound){
        if(a<b) ret={change,b,0};
        else if(a>c) ret={change,c,0};
        else ret={change,a,0};
    }
    return ret;
}
ura Bound(int i,int j)
{
    ura ret;
    int a,b,c,d;
    a=lazy[i].var1;
    b=lazy[i].var2;
    c=lazy[j].var1;
    d=lazy[j].var2;
    if(lazy[j].type==add){
        if(c<a) ret={bound,a,b};
        else if(c>b) ret={change,c,0};
        else ret={bound,c,b};
    }
    else if(lazy[j].type==rem){
        if(c<a) ret={change,c,0};
        else if(c>b) ret={bound,a,b};
        else ret={bound,a,c};
    }
    else if(lazy[j].type==change){
        ret={change,c,0};
    }
    else if(lazy[j].type==bound){
        if(b<c) ret={change,c,0};
        else if(b>=c && b<=d && a<c) ret={bound,c,b};
        else if(b>=c && b<=d && a>=c && a<=d) ret={bound,a,b};
        else if(b>d && a>=c && a<=d) ret={bound,a,d};
        else if(d<a) ret={change,d,0};
    }
    return ret;
}
ura combine(int i,int j)
{
    if(lazy[i].type==0)
        return lazy[j];
    if(lazy[i].type==add)
        return Add(i,j);
    if(lazy[i].type==rem)
        return Remove(i,j);
    if(lazy[i].type==change)
        return Change(i,j);
    if(lazy[i].type==bound)
        return Bound(i,j);
}
void propagate(int i,int L,int R)
{
    if(lazy[i].type==0) return;
    if(lazy[i].type==add) segm_tree[i]=max(segm_tree[i],lazy[i].var1);
    else if(lazy[i].type==rem) segm_tree[i]=min(segm_tree[i],lazy[i].var1);
    else if(lazy[i].type==change) segm_tree[i]=lazy[i].var1;
    else if(lazy[i].type==bound){
        if(segm_tree[i]<lazy[i].var1)
            segm_tree[i]=lazy[i].var1;
        else if(segm_tree[i]>lazy[i].var2)
            segm_tree[i]=lazy[i].var2;
    }
    if(L<R){

        lazy[leftNode(i)]=combine(leftNode(i),i);
        lazy[rightNode(i)]=combine(rightNode(i),i);
    }
    lazy[i].type=0;
}
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)
        lazy[i].type=type,lazy[i].var1=h;
    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);
    }
}

Compilation message (stderr)

wall.cpp: In function 'ura combine(int, int)':
wall.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39