oj.uz

Submission #147271

# Submission time Handle Problem Language Result Execution time Memory
147271 2019-08-28T16:17:51 Z Kamisama Wall (IOI14_wall) C++14
100 / 100
 1975 ms 132416 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define CL(x) (x<<1)
#define CR(x) (x<<1|1)
using namespace std;
const int maxn=2e6+7;
const int inf=1e9+7;

class SegmentTree{
private:
    int low,high,mn,mx,pos,l[4*maxn],r[4*maxn];
    struct Nodes{
        int min,max;
        inline Nodes(int _min=0, int _max=0){
            tie(min,max)=tie(_min,_max);
        }
    }it[4*maxn];
public:
    inline void Combine(const int &x){
        it[x].min=min(it[CL(x)].min,it[CR(x)].min);
        it[x].max=max(it[CL(x)].max,it[CR(x)].max);
    }

    inline void Build(const int &x, const int &low, const int &high){
        l[x]=low; r[x]=high;
        if(low==high) it[x]=Nodes(0,0);
        else{
            int mid=(low+high)>>1;
            Build(CL(x),low,mid);
            Build(CR(x),mid+1,high);
            Combine(x);
        }
    }

    inline void Modify(const int &x, const int &mn, const int &mx){
        if(it[x].min>mx) it[x].min=it[x].max=mx;
        else if(it[x].max<mn) it[x].min=it[x].max=mn;
        else{
            it[x].min=max(it[x].min,mn);
            it[x].max=min(it[x].max,mx);
        }
    }

    inline void PushDown(const int &x){
        if(x!=1) Modify(x,it[x>>1].min,it[x>>1].max);
    }

    inline void Update(const int &x){
        PushDown(x);
        if(l[x]>high || r[x]<low) return;
        if(low<=l[x] && r[x]<=high) Modify(x,mn,mx);
        else{
            Update(CL(x));
            Update(CR(x));
            Combine(x);
        }
    }

    inline void Update(const int &i, const int &j, const int &min, const int &max){
        tie(low,high,mn,mx)=tie(i,j,min,max);
        Update(1);
    }

    inline int Query(const int &x){
        if(l[x]>pos || r[x]<pos) return inf;
        PushDown(x);
        if(l[x]==r[x]) return it[x].min;
        return min(Query(CL(x)),Query(CR(x)));
    }

    inline int Get(const int &x){
        return pos=x,Query(1);
    }
}seg_tree;

int n,k;
int op[maxn],left[maxn],right[maxn],height[maxn],finalHeight[maxn];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    seg_tree.Build(1,0,n-1);
    for(int i=0;i<k;i++){
        if(op[i]==1) seg_tree.Update(left[i],right[i],height[i],inf);
        else seg_tree.Update(left[i],right[i],0,height[i]);
    }
    for(int i=0;i<n;i++) finalHeight[i]=seg_tree.Get(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62968 KB Output is correct
2 Correct 59 ms 63216 KB Output is correct
3 Correct 59 ms 63096 KB Output is correct
4 Correct 69 ms 63480 KB Output is correct
5 Correct 67 ms 63468 KB Output is correct
6 Correct 65 ms 63480 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62968 KB Output is correct
2 Correct 226 ms 76668 KB Output is correct
3 Correct 376 ms 70756 KB Output is correct
4 Correct 1038 ms 77460 KB Output is correct
5 Correct 600 ms 84188 KB Output is correct
6 Correct 573 ms 82808 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 62964 KB Output is correct
2 Correct 59 ms 63224 KB Output is correct
3 Correct 59 ms 63096 KB Output is correct
4 Correct 70 ms 63608 KB Output is correct
5 Correct 66 ms 63480 KB Output is correct
6 Correct 66 ms 63460 KB Output is correct
7 Correct 57 ms 62940 KB Output is correct
8 Correct 226 ms 76664 KB Output is correct
9 Correct 367 ms 70648 KB Output is correct
10 Correct 1030 ms 83064 KB Output is correct
11 Correct 583 ms 84208 KB Output is correct
12 Correct 571 ms 82776 KB Output is correct
13 Correct 56 ms 62968 KB Output is correct
14 Correct 228 ms 76664 KB Output is correct
15 Correct 114 ms 64728 KB Output is correct
16 Correct 1137 ms 83360 KB Output is correct
17 Correct 586 ms 82860 KB Output is correct
18 Correct 580 ms 82820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 63124 KB Output is correct
2 Correct 58 ms 63068 KB Output is correct
3 Correct 59 ms 63024 KB Output is correct
4 Correct 71 ms 63480 KB Output is correct
5 Correct 66 ms 63480 KB Output is correct
6 Correct 65 ms 63496 KB Output is correct
7 Correct 56 ms 62956 KB Output is correct
8 Correct 225 ms 76640 KB Output is correct
9 Correct 374 ms 70748 KB Output is correct
10 Correct 1022 ms 83064 KB Output is correct
11 Correct 579 ms 84180 KB Output is correct
12 Correct 571 ms 82568 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 228 ms 76544 KB Output is correct
15 Correct 115 ms 64632 KB Output is correct
16 Correct 1149 ms 83412 KB Output is correct
17 Correct 590 ms 82808 KB Output is correct
18 Correct 580 ms 82816 KB Output is correct
19 Correct 1975 ms 132296 KB Output is correct
20 Correct 1936 ms 129784 KB Output is correct
21 Correct 1945 ms 132416 KB Output is correct
22 Correct 1933 ms 129760 KB Output is correct
23 Correct 1930 ms 130040 KB Output is correct
24 Correct 1935 ms 129724 KB Output is correct
25 Correct 1943 ms 129692 KB Output is correct
26 Correct 1953 ms 132300 KB Output is correct
27 Correct 1937 ms 132204 KB Output is correct
28 Correct 1937 ms 129784 KB Output is correct
29 Correct 1939 ms 129784 KB Output is correct
30 Correct 1942 ms 129784 KB Output is correct