oj.uz

Submission #1012050

# Submission time Handle Problem Language Result Execution time Memory
1012050 2024-07-01T15:06:38 Z doducanh Wall (IOI14_wall) C++14
0 / 100
 80 ms 15968 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=5e5+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*3+7,0),lazy(n*3+7){}
    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;
        }
        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;
        }
        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);}
};
int n,k;
int op[maxn],le[maxn],ri[maxn],height[maxn];
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(le[i],ri[i],height[i],op[i]);
    }
    t.get();
    for(int i=0;i<n;i++)finalHeight[i]=res[i];

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 1 ms 2552 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 80 ms 15968 KB Output is correct
3 Incorrect 57 ms 10068 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -