oj.uz

Submission #843997

# Submission time Handle Problem Language Result Execution time Memory
843997 2023-09-04T20:44:40 Z Mr_Ph Wall (IOI14_wall) C++14
100 / 100
 1064 ms 92360 KB 
#include "wall.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
struct item
{
    int mn;
    int mx;
};
struct segtree
{
    int siz=1;
    vector<item>vals;
    vector<item>lazy;
    void init(int n)
    {
        while(siz<n)
            siz*=2;
        vals.resize(4*siz);
    }
    item mrg(item a,item b)
    {
        a.mn=min(a.mn,b.mn);
        a.mn=max(a.mn,b.mx);
        a.mx=max(a.mx,b.mx);
        a.mx=min(a.mx,b.mn);
        return a;
    }
    void updaterage(int l,int r,int v,int op,int x,int lx,int rx)
    {
        if(lx>r||rx<l)return ;
        if(lx>=l&&rx<=r)
        {
            if(op==1)
            {
                vals[x].mn=max(vals[x].mn,v);
                vals[x].mx=max(vals[x].mx,v);
            }
            else
            {
                vals[x].mn=min(vals[x].mn,v);
                vals[x].mx=min(vals[x].mx,v);
            }
            return;
        }

        vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
        vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
        vals[x].mn=1e9,vals[x].mx=0;
        int mid=(lx+rx+1)/2;
        updaterage(l,r,v,op,2*x+1,lx,mid-1);
        updaterage(l,r,v,op,2*x+2,mid,rx);
    }
    void updaterage(int l,int r,int v,int op)
    {
        updaterage(l,r,v,op,0,0,siz-1);
    }
    int calc(int l,int r,int x,int lx,int rx)
    {
        vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
        vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
        if(lx>r||rx<l)return 1e9;
        if(lx>=l&&rx<=r)return min(vals[x].mn,vals[x].mx);
        int mid=(lx+rx+1)/2;
        return min(calc(l,r,2*x+1,lx,mid-1),calc(l,r,2*x+2,mid,rx));
    }
    int calc(int l,int r)
    {
        return calc(l,r,0,0,siz-1);
    }
};
void buildWall(int n, int k, int x[], int l[], int r[], int h[], int ans[])
{
    segtree st;
    st.init(n);
    for(int i=0; i<k; i++)
    {
        st.updaterage(l[i],r[i],h[i],x[i]);
    }
    for(int i=0; i<n; i++)
        ans[i]=st.calc(i,i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 1112 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct
6 Correct 6 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 115 ms 13904 KB Output is correct
3 Correct 127 ms 8548 KB Output is correct
4 Correct 353 ms 22352 KB Output is correct
5 Correct 242 ms 22868 KB Output is correct
6 Correct 232 ms 21328 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 8 ms 1112 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 113 ms 14060 KB Output is correct
9 Correct 125 ms 8528 KB Output is correct
10 Correct 351 ms 22352 KB Output is correct
11 Correct 238 ms 22864 KB Output is correct
12 Correct 242 ms 21328 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 114 ms 13936 KB Output is correct
15 Correct 24 ms 2392 KB Output is correct
16 Correct 358 ms 22352 KB Output is correct
17 Correct 247 ms 21704 KB Output is correct
18 Correct 239 ms 21660 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct
6 Correct 6 ms 1112 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 110 ms 13856 KB Output is correct
9 Correct 125 ms 8552 KB Output is correct
10 Correct 354 ms 22216 KB Output is correct
11 Correct 244 ms 22780 KB Output is correct
12 Correct 235 ms 21220 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 115 ms 13904 KB Output is correct
15 Correct 24 ms 2392 KB Output is correct
16 Correct 356 ms 22352 KB Output is correct
17 Correct 242 ms 21584 KB Output is correct
18 Correct 245 ms 21876 KB Output is correct
19 Correct 1059 ms 91984 KB Output is correct
20 Correct 1039 ms 91936 KB Output is correct
21 Correct 1064 ms 92360 KB Output is correct
22 Correct 1055 ms 92220 KB Output is correct
23 Correct 1046 ms 92012 KB Output is correct
24 Correct 1059 ms 91984 KB Output is correct
25 Correct 1037 ms 92308 KB Output is correct
26 Correct 1037 ms 92236 KB Output is correct
27 Correct 1043 ms 91984 KB Output is correct
28 Correct 1045 ms 92028 KB Output is correct
29 Correct 1042 ms 92116 KB Output is correct
30 Correct 1035 ms 91984 KB Output is correct