oj.uz

Submission #1012068

# Submission time Handle Problem Language Result Execution time Memory
1012068 2024-07-01T15:23:58 Z doducanh Wall (IOI14_wall) C++14
100 / 100
 351 ms 128400 KB 
#include <bits/stdc++.h>

using namespace std;
#define lc (id<<1)
#define rc ((id<<1)|1)
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=2e6+7;
const int inf=1e9+7;
int res[maxn];
struct segtree{
    int n;
    vector<int>t;
    vector<pair<int,int>>lazy;
    segtree(){}
    segtree(int n):n(n),t(n*4+7,0),lazy(n*4+7,{0,0}){}
    void pulldec(int x,int k)
    {
        t[x]=min(t[x],k);
        lazy[x].fi=min(lazy[x].fi,k);
        lazy[x].se=min(lazy[x].se,k);
    }
    void pulladd(int x,int k)
    {
        t[x]=max(t[x],k);
        lazy[x].fi=max(lazy[x].fi,k);
        lazy[x].se=max(lazy[x].se,k);
    }
    void down(int id){
        if(lazy[id].fi!=-inf){
            pulladd(lc,lazy[id].fi);
            pulladd(rc,lazy[id].fi);
        }
        if(lazy[id].se!=inf){
            pulldec(lc,lazy[id].se);
            pulldec(rc,lazy[id].se);
        }
        lazy[id]={-inf,inf};
    }
    void up(int id,int l,int r,int u,int v,int k,int type){
        if(l>v||r<u){
            return;
        }
        if(u<=l&&r<=v){
            if(type==1)pulladd(id,k);
            else pulldec(id,k);
            return;
        }
        if(l!=r)down(id);
        int m=(l+r)/2;
        up(lc,l,m,u,v,k,type);
        up(rc,m+1,r,u,v,k,type);
    }
    void get(int id,int l,int r){
        if(l==r){
            res[l]=t[id];
            return;
        }
        if(l!=r)down(id);
        int m=(l+r)/2;
        get(lc,l,m);
        get(rc,m+1,r);
    }
    void up(int u,int v,int k,int type){up(1,0,n-1,u,v,k,type);}
    void get(){get(1,0,n-1);}
};
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    segtree t(n);
    for(int i=0;i<k;i++){
        t.up(left[i],right[i],height[i],op[i]);
    }
    t.get();
    for(int i=0;i<n;i++)finalHeight[i]=res[i];

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 3 ms 1132 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 73 ms 14044 KB Output is correct
3 Correct 88 ms 8268 KB Output is correct
4 Correct 271 ms 23208 KB Output is correct
5 Correct 145 ms 23892 KB Output is correct
6 Correct 134 ms 22100 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 3 ms 1140 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 13956 KB Output is correct
9 Correct 96 ms 8416 KB Output is correct
10 Correct 267 ms 23124 KB Output is correct
11 Correct 138 ms 23748 KB Output is correct
12 Correct 128 ms 22124 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 84 ms 13960 KB Output is correct
15 Correct 18 ms 2396 KB Output is correct
16 Correct 324 ms 23168 KB Output is correct
17 Correct 139 ms 22608 KB Output is correct
18 Correct 136 ms 22608 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 78 ms 13928 KB Output is correct
9 Correct 97 ms 8276 KB Output is correct
10 Correct 272 ms 23120 KB Output is correct
11 Correct 158 ms 23900 KB Output is correct
12 Correct 128 ms 22256 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 77 ms 13908 KB Output is correct
15 Correct 19 ms 2392 KB Output is correct
16 Correct 331 ms 23192 KB Output is correct
17 Correct 149 ms 22640 KB Output is correct
18 Correct 143 ms 22640 KB Output is correct
19 Correct 346 ms 128084 KB Output is correct
20 Correct 334 ms 128036 KB Output is correct
21 Correct 351 ms 128124 KB Output is correct
22 Correct 332 ms 128080 KB Output is correct
23 Correct 339 ms 128084 KB Output is correct
24 Correct 336 ms 128076 KB Output is correct
25 Correct 350 ms 128400 KB Output is correct
26 Correct 330 ms 128084 KB Output is correct
27 Correct 340 ms 128084 KB Output is correct
28 Correct 350 ms 128080 KB Output is correct
29 Correct 339 ms 128080 KB Output is correct
30 Correct 340 ms 128224 KB Output is correct