Submission #608350

#	Time	Username	Problem	Language	Result	Execution time	Memory
608350		NicolaAbusaad2014	Wall (IOI14_wall)	C++14	0 / 100	229 ms	13860 KiB

wall

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

using namespace std;

struct segment_tree
{
    struct node
    {
        long long mx,mn,left,right;
    };
    node dum;
    vector<node>tree;
    vector<long long>upd;
    node operation(node x,node z)
    {
        node ret;
        ret.mx=max(x.mx,z.mx);
        ret.mn=max(x.mn,z.mn);
        ret.left=min(x.left,z.left);
        ret.right=max(x.right,z.right);
        return ret;
    }
    void push(long node)
    {
        if(node<tree[0].mx){
            tree[node*2].mx=min(tree[node].mx,tree[node*2].mx);
            tree[node*2].mn=max(tree[node].mn,tree[node*2].mn);
            tree[node*2+1].mx=min(tree[node].mx,tree[node*2+1].mx);
            tree[node*2+1].mn=max(tree[node].mn,tree[node*2+1].mn);
        }
    }
    void build(vector<long long>v)
    {
        tree.clear();
        upd.clear();
        long long x=((v.size())*2)-1;
        while(x&(x-1)){
            x=x&(x-1);
        }
        tree.resize(x*2);
        upd.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++){
            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++){
            tree[i+x].left=i;
            tree[i+x].right=i;
        }
        for(long i=x-1;i>0;i--){
            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){
            tree[node].mn=max(tree[node].mn,z);
            tree[node].mx=max(tree[node].mn,tree[node].mx);
            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){
            tree[node].mx=min(tree[node].mx,z);
            tree[node].mn=min(tree[node].mn,tree[node].mx);
            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:48: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]
   48 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~

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