oj.uz

Submission #472705

# Submission time Handle Problem Language Result Execution time Memory
472705 2021-09-14T08:11:13 Z Haidara Wall (IOI14_wall) C++17
100 / 100
 1184 ms 99400 KB 
#include "wall.h"
#include<algorithm>
using namespace std;
const int maxn=2000001,inf=1e9+7;
struct segtree
{
    int mx,mn;
    segtree():mn(0),mx(inf){}
} st[maxn*4];
bool add=0;
void pull(int inx)
{
    st[inx*2].mn=max(min(st[inx].mx,st[inx*2].mn),st[inx].mn);
    st[inx*2].mx=min(max(st[inx*2].mx,st[inx].mn),st[inx].mx);
    st[inx*2+1].mn=max(min(st[inx*2+1].mn,st[inx].mx),st[inx].mn);
    st[inx*2+1].mx=min(max(st[inx*2+1].mx,st[inx].mn),st[inx].mx);
    st[inx].mn=0;
    st[inx].mx=inf;
}
void update(int ul,int ur,int val,int l,int r,int inx=1)
{
    if(ul<=l&&r<=ur)
    {
        if(add)
        {
            st[inx].mn=max(st[inx].mn,val);
            st[inx].mx=max(st[inx].mn,st[inx].mx);
        }
        else
        {
            st[inx].mx=min(st[inx].mx,val);
            st[inx].mn=min(st[inx].mn,st[inx].mx);
        }
        if(l!=r)
            pull(inx);
        return ;
    }
    if(l>ur||ul>r)
        return ;
    pull(inx);
    int mid=l+(r-l)/2;
    update(ul,ur,val,l,mid,inx*2);
    update(ul,ur,val,mid+1,r,inx*2+1);
}
int query(int pos,int l,int r,int inx=1)
{
    if(l==r)
        return st[inx].mn;
    int mid=l+(r-l)/2;
    pull(inx);
    if(pos<=mid)
        return query(pos,l,mid,inx*2);
    return query(pos,mid+1,r,inx*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    for(int i=0; i<k; i++)
    {
        if(op[i]==1)
            add=1;
        else
            add=0;
        update(left[i]+1,right[i]+1,height[i],1,n);
    }
    for(int i=0; i<n; i++)
        finalHeight[i]=query(i+1,1,n);
}

Compilation message

wall.cpp: In constructor 'segtree::segtree()':
wall.cpp:7:12: warning: 'segtree::mn' will be initialized after [-Wreorder]
    7 |     int mx,mn;
      |            ^~
wall.cpp:7:9: warning:   'int segtree::mx' [-Wreorder]
    7 |     int mx,mn;
      |         ^~
wall.cpp:8:5: warning:   when initialized here [-Wreorder]
    8 |     segtree():mn(0),mx(inf){}
      |     ^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62796 KB Output is correct
2 Correct 35 ms 62932 KB Output is correct
3 Correct 34 ms 62916 KB Output is correct
4 Correct 39 ms 63052 KB Output is correct
5 Correct 43 ms 63140 KB Output is correct
6 Correct 39 ms 63044 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62876 KB Output is correct
2 Correct 201 ms 71372 KB Output is correct
3 Correct 254 ms 67012 KB Output is correct
4 Correct 599 ms 72008 KB Output is correct
5 Correct 372 ms 72132 KB Output is correct
6 Correct 359 ms 72136 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62856 KB Output is correct
2 Correct 36 ms 62952 KB Output is correct
3 Correct 37 ms 62828 KB Output is correct
4 Correct 46 ms 63128 KB Output is correct
5 Correct 40 ms 63104 KB Output is correct
6 Correct 46 ms 63044 KB Output is correct
7 Correct 35 ms 62876 KB Output is correct
8 Correct 189 ms 71092 KB Output is correct
9 Correct 219 ms 66596 KB Output is correct
10 Correct 568 ms 71620 KB Output is correct
11 Correct 372 ms 72088 KB Output is correct
12 Correct 350 ms 72100 KB Output is correct
13 Correct 36 ms 62888 KB Output is correct
14 Correct 186 ms 71092 KB Output is correct
15 Correct 64 ms 63880 KB Output is correct
16 Correct 598 ms 71976 KB Output is correct
17 Correct 362 ms 71884 KB Output is correct
18 Correct 367 ms 72036 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62788 KB Output is correct
2 Correct 36 ms 62992 KB Output is correct
3 Correct 36 ms 62820 KB Output is correct
4 Correct 42 ms 63128 KB Output is correct
5 Correct 41 ms 63028 KB Output is correct
6 Correct 40 ms 63144 KB Output is correct
7 Correct 34 ms 62804 KB Output is correct
8 Correct 188 ms 71088 KB Output is correct
9 Correct 214 ms 66636 KB Output is correct
10 Correct 559 ms 71660 KB Output is correct
11 Correct 360 ms 72180 KB Output is correct
12 Correct 355 ms 72132 KB Output is correct
13 Correct 35 ms 62772 KB Output is correct
14 Correct 196 ms 71108 KB Output is correct
15 Correct 76 ms 63828 KB Output is correct
16 Correct 549 ms 71968 KB Output is correct
17 Correct 386 ms 72004 KB Output is correct
18 Correct 365 ms 71872 KB Output is correct
19 Correct 1097 ms 89096 KB Output is correct
20 Correct 1123 ms 96736 KB Output is correct
21 Correct 1184 ms 99236 KB Output is correct
22 Correct 1124 ms 96972 KB Output is correct
23 Correct 1104 ms 96708 KB Output is correct
24 Correct 1109 ms 96900 KB Output is correct
25 Correct 1109 ms 96832 KB Output is correct
26 Correct 1117 ms 99400 KB Output is correct
27 Correct 1124 ms 99208 KB Output is correct
28 Correct 1101 ms 96688 KB Output is correct
29 Correct 1106 ms 96800 KB Output is correct
30 Correct 1103 ms 96940 KB Output is correct