oj.uz

Submission #480656

# Submission time Handle Problem Language Result Execution time Memory
480656 2021-10-17T14:16:28 Z Haidara Wall (IOI14_wall) C++17
100 / 100
 1063 ms 99328 KB 
#include<bits/stdc++.h>
#include<wall.h>
#define v(i) vector< i >
using namespace std;
const int maxn=2000001;
int n;
const int inf=INT_MAX;
struct node
{
    int mx,mn;
    node():mx(inf),mn(0) {}
} st[maxn*4];
void pull(int inx)
{
    st[inx*2].mn=max(st[inx].mn,min(st[inx*2].mn,st[inx].mx));
    st[inx*2].mx=min(st[inx].mx,max(st[inx*2].mx,st[inx].mn));
    st[inx*2+1].mn=max(st[inx].mn,min(st[inx*2+1].mn,st[inx].mx));
    st[inx*2+1].mx=min(st[inx].mx,max(st[inx*2+1].mx,st[inx].mn));
    st[inx].mn=0,st[inx].mx=inf;
}
bool go;
void add(int ql,int qr,int val,int l=0,int r=n-1,int inx=1)
{
    if(ql<=l&&r<=qr)
    {
        if(go)
        {
            st[inx].mn=max(st[inx].mn,val);
            st[inx].mx=max(st[inx].mx,val);
        }
        else 
        {
            st[inx].mx=min(val,st[inx].mx);
            st[inx].mn=min(val,st[inx].mn);
        }
        if(l!=r)
        pull(inx);
        return ;
    }
    if(ql>r||l>qr)
        return ;
    pull(inx);
    int mid=l+(r-l)/2;
    add(ql,qr,val,l,mid,inx*2);
    add(ql,qr,val,mid+1,r,inx*2+1);
}
int query(int pos,int l=0,int r=n-1,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[])
{
    n=N;
    for(int i=0; i<k; i++)
    {
        if(op[i]&1)
        	go=1;
    	else 
    		go=0;
        add(left[i],right[i],height[i]);
    }
    for(int i=0; i<n; i++)
        finalHeight[i]=query(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62796 KB Output is correct
2 Correct 33 ms 62948 KB Output is correct
3 Correct 32 ms 62916 KB Output is correct
4 Correct 38 ms 63048 KB Output is correct
5 Correct 37 ms 62984 KB Output is correct
6 Correct 45 ms 63024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62912 KB Output is correct
2 Correct 168 ms 70696 KB Output is correct
3 Correct 189 ms 66284 KB Output is correct
4 Correct 486 ms 71260 KB Output is correct
5 Correct 351 ms 71944 KB Output is correct
6 Correct 313 ms 71772 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62908 KB Output is correct
2 Correct 32 ms 62916 KB Output is correct
3 Correct 31 ms 62916 KB Output is correct
4 Correct 36 ms 62968 KB Output is correct
5 Correct 41 ms 63016 KB Output is correct
6 Correct 39 ms 63024 KB Output is correct
7 Correct 33 ms 62888 KB Output is correct
8 Correct 170 ms 70724 KB Output is correct
9 Correct 194 ms 66188 KB Output is correct
10 Correct 489 ms 71228 KB Output is correct
11 Correct 325 ms 71900 KB Output is correct
12 Correct 321 ms 71808 KB Output is correct
13 Correct 32 ms 62852 KB Output is correct
14 Correct 177 ms 70724 KB Output is correct
15 Correct 57 ms 63456 KB Output is correct
16 Correct 529 ms 71532 KB Output is correct
17 Correct 314 ms 71644 KB Output is correct
18 Correct 334 ms 71528 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62796 KB Output is correct
2 Correct 31 ms 62936 KB Output is correct
3 Correct 32 ms 62924 KB Output is correct
4 Correct 40 ms 63004 KB Output is correct
5 Correct 39 ms 63008 KB Output is correct
6 Correct 40 ms 63040 KB Output is correct
7 Correct 32 ms 62800 KB Output is correct
8 Correct 165 ms 70724 KB Output is correct
9 Correct 203 ms 66204 KB Output is correct
10 Correct 485 ms 71340 KB Output is correct
11 Correct 316 ms 71784 KB Output is correct
12 Correct 314 ms 71776 KB Output is correct
13 Correct 32 ms 62796 KB Output is correct
14 Correct 180 ms 70724 KB Output is correct
15 Correct 62 ms 63428 KB Output is correct
16 Correct 481 ms 71492 KB Output is correct
17 Correct 332 ms 71612 KB Output is correct
18 Correct 314 ms 71528 KB Output is correct
19 Correct 1026 ms 88976 KB Output is correct
20 Correct 1022 ms 96924 KB Output is correct
21 Correct 1022 ms 99256 KB Output is correct
22 Correct 1032 ms 96792 KB Output is correct
23 Correct 1027 ms 96828 KB Output is correct
24 Correct 1031 ms 96824 KB Output is correct
25 Correct 1063 ms 96836 KB Output is correct
26 Correct 1048 ms 99220 KB Output is correct
27 Correct 1039 ms 99328 KB Output is correct
28 Correct 1026 ms 96820 KB Output is correct
29 Correct 1058 ms 96880 KB Output is correct
30 Correct 1012 ms 96844 KB Output is correct