oj.uz

Submission #608583

# Submission time Handle Problem Language Result Execution time Memory
608583 2022-07-27T08:31:30 Z NicolaAbusaad2014 Wall (IOI14_wall) C++14
100 / 100
 1762 ms 132732 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

struct segment_tree
{
    struct node
    {
        int mx,mn,left,right;
    };
    int inf=1e9;
    node dum;
    vector<node>tree;
    vector<int>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(int node)
    {
        if(upd_mn[node]==inf&&upd_mx[node]==-inf){
            return;
        }
        if(upd_mn[node]==inf){
            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_mx[node*2]=max(upd_mx[node],upd_mx[node*2]);
                upd_mn[node*2]=max(upd_mx[node],upd_mn[node*2]);
                upd_mx[node*2+1]=max(upd_mx[node],upd_mx[node*2+1]);
                upd_mn[node*2+1]=max(upd_mx[node],upd_mn[node*2+1]);
            }
            upd_mx[node]=-inf;
            return;
        }
        if(upd_mx[node]==-inf){
            tree[node].mx=min(tree[node].mx,upd_mn[node]);
            tree[node].mn=min(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]=min(upd_mn[node],upd_mx[node*2]);
                upd_mn[node*2+1]=min(upd_mn[node],upd_mn[node*2+1]);
                upd_mx[node*2+1]=min(upd_mn[node],upd_mx[node*2+1]);
            }
            upd_mn[node]=inf;
            return;
        }
        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<int>v)
    {
        tree.clear();
        upd_mn.clear();
        upd_mx.clear();
        int 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(int 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(int 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(int 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(int l,int r,int 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(int l,int r,int z,int 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(int l,int r,int z,int 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<int>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

wall.cpp: In member function 'void segment_tree::build(std::vector<int>)':
wall.cpp:86:18: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   86 |         dum.left=-1e18;
      |                  ^~~~~
wall.cpp:87:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   87 |         dum.right=1e18;
      |                   ^~~~
wall.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i=0;i<v.size();i++){
      |                     ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 12 ms 1236 KB Output is correct
5 Correct 12 ms 1236 KB Output is correct
6 Correct 8 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 135 ms 8012 KB Output is correct
3 Correct 261 ms 5300 KB Output is correct
4 Correct 829 ms 15072 KB Output is correct
5 Correct 345 ms 15200 KB Output is correct
6 Correct 337 ms 15020 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1236 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 10 ms 1236 KB Output is correct
7 Correct 0 ms 284 KB Output is correct
8 Correct 157 ms 8044 KB Output is correct
9 Correct 258 ms 5364 KB Output is correct
10 Correct 761 ms 15076 KB Output is correct
11 Correct 332 ms 15076 KB Output is correct
12 Correct 327 ms 15028 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 144 ms 8028 KB Output is correct
15 Correct 52 ms 2476 KB Output is correct
16 Correct 1006 ms 15164 KB Output is correct
17 Correct 346 ms 15076 KB Output is correct
18 Correct 377 ms 15020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1236 KB Output is correct
5 Correct 11 ms 1236 KB Output is correct
6 Correct 10 ms 1240 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 137 ms 8092 KB Output is correct
9 Correct 256 ms 5316 KB Output is correct
10 Correct 718 ms 15080 KB Output is correct
11 Correct 331 ms 15080 KB Output is correct
12 Correct 332 ms 15080 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 136 ms 8056 KB Output is correct
15 Correct 54 ms 2472 KB Output is correct
16 Correct 1016 ms 15060 KB Output is correct
17 Correct 358 ms 15080 KB Output is correct
18 Correct 369 ms 15052 KB Output is correct
19 Correct 1433 ms 122380 KB Output is correct
20 Correct 1467 ms 132628 KB Output is correct
21 Correct 1515 ms 132668 KB Output is correct
22 Correct 1447 ms 132660 KB Output is correct
23 Correct 1437 ms 132700 KB Output is correct
24 Correct 1629 ms 132724 KB Output is correct
25 Correct 1522 ms 132720 KB Output is correct
26 Correct 1762 ms 132616 KB Output is correct
27 Correct 1504 ms 132700 KB Output is correct
28 Correct 1641 ms 132688 KB Output is correct
29 Correct 1604 ms 132648 KB Output is correct
30 Correct 1589 ms 132732 KB Output is correct