Submission #608553

#	Time	Username	Problem	Language	Result	Execution time	Memory
608553		NicolaAbusaad2014	Wall (IOI14_wall)	C++14	61 / 100	3103 ms	246888 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

struct segment_tree
{
    struct node
    {
        long long mx,mn,left,right;
    };
    long long inf=1e18;
    node dum;
    vector<node>tree;
    vector<long long>upd_mn,upd_mx;
    node operation(node x,node z)
    {
        node ret;
        ret.mx=max(x.mx,z.mx);
        ret.mn=min(x.mn,z.mn);
        ret.left=min(x.left,z.left);
        ret.right=max(x.right,z.right);
        return ret;
    }
    void push(long node)
    {
            tree[node].mx=min(tree[node].mx,upd_mn[node]);
            tree[node].mn=min(tree[node].mn,tree[node].mx);
            tree[node].mn=max(tree[node].mn,upd_mx[node]);
            tree[node].mx=max(tree[node].mn,tree[node].mx);
            if(node<tree[0].mx){
                upd_mn[node*2]=min(upd_mn[node],upd_mn[node*2]);
                upd_mx[node*2]=max(upd_mx[node],upd_mx[node*2]);
                upd_mx[node*2]=min(upd_mn[node],upd_mx[node*2]);
                upd_mn[node*2]=max(upd_mx[node],upd_mn[node*2]);
                upd_mn[node*2+1]=min(upd_mn[node],upd_mn[node*2+1]);
                upd_mx[node*2+1]=max(upd_mx[node],upd_mx[node*2+1]);
                upd_mx[node*2+1]=min(upd_mn[node],upd_mx[node*2+1]);
                upd_mn[node*2+1]=max(upd_mx[node],upd_mn[node*2+1]);
            }
            upd_mn[node]=inf;
            upd_mx[node]=-inf;
    }
    void build(vector<long long>v)
    {
        tree.clear();
        upd_mn.clear();
        upd_mx.clear();
        long long x=((v.size())*2)-1;
        while(x&(x-1)){
            x=x&(x-1);
        }
        tree.resize(x*2);
        upd_mn.resize(x*2);
        upd_mx.resize(x*2);
        tree[0].mx=x;
        dum.mx=0;
        dum.mn=0;
        dum.left=-1e18;
        dum.right=1e18;
        for(long i=0;i<v.size();i++){
            upd_mn[i]=inf;
            upd_mx[i]=-inf;
            tree[i+x].mx=v[i];
            tree[i+x].mn=v[i];
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=v.size();i<x;i++){
            upd_mn[i]=inf;
            upd_mx[i]=-inf;
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=x-1;i>0;i--){
            upd_mn[i]=inf;
            upd_mx[i]=-inf;
            tree[i]=operation(tree[i*2],tree[(i*2)+1]);
        }
    }
    node get(long long l,long long r,long node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return dum;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            return tree[node];
        }
        return operation(get(l,r,node*2),get(l,r,(node*2)+1));
    }
    void update_mx(long long l,long long r,long long z,long long node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            upd_mx[node]=z;
            push(node);
            return;
        }
        update_mx(l,r,z,node*2);
        update_mx(l,r,z,(node*2)+1);
        tree[node]=operation(tree[node*2],tree[(node*2)+1]);
    }
    void update_mn(long long l,long long r,long long z,long long node=1)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            upd_mn[node]=z;
            push(node);
            return;
        }
        update_mn(l,r,z,node*2);
        update_mn(l,r,z,(node*2)+1);
        tree[node]=operation(tree[node*2],tree[(node*2)+1]);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<long long>dum(n);
    segment_tree st;
    st.build(dum);
    for(int i=0;i<k;i++){
        if(op[i]==1){
            st.update_mx(left[i],right[i],height[i]);
            continue;
        }
        st.update_mn(left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=st.get(i,i).mx;
    }
    return;
}

Compilation message (stderr)

wall.cpp: In member function 'void segment_tree::build(std::vector<long long int>)':
wall.cpp:61:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~

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