oj.uz

Submission #881836

# Submission time Handle Problem Language Result Execution time Memory
881836 2023-12-02T03:36:45 Z cpptowin Wall (IOI14_wall) C++17
0 / 100
 409 ms 26048 KB 
#include<bits/stdc++.h>
#include<wall.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define inf 1000000000
using namespace std;
int st[maxn];
int lazy1[maxn],lazy[maxn];
void down(int id)
{
    if(lazy[id])
    {
        st[id << 1] = max(st[id << 1],lazy[id]);
        st[id << 1 | 1] = max(st[id << 1 | 1],lazy[id]);
        lazy[id << 1] = max(lazy[id],lazy[id << 1]);
        lazy[id << 1 | 1] = max(lazy[id << 1 | 1],lazy[id]);
        lazy1[id << 1] = lazy1[id << 1 | 1] = -1;
        lazy[id] = 0;
    }
    if(lazy1[id] != -1)
    {
        st[id << 1] = min(st[id << 1],lazy1[id]);
        st[id << 1 | 1] = min(st[id << 1 | 1],lazy1[id]);
        if(lazy1[id << 1] == -1) lazy1[id << 1] = lazy1[id];
        else  lazy1[id << 1] = min(lazy1[id],lazy1[id << 1]);
        if(lazy1[id << 1 | 1] == -1) lazy1[id << 1 | 1] = lazy1[id];
        else  lazy1[id << 1 | 1] = min(lazy1[id],lazy1[id << 1 | 1]);
        lazy1[id] = -1;
        lazy[id << 1] = lazy[id << 1 | 1] = 0;
    }
}
void update_max(int id,int l,int r,int u,int v,int val)
{
    if(l > v or r < u) return;
    if(u <= l and r <= v)
    {
        st[id] = max(st[id],val);
        lazy[id] = max(lazy[id],val);
        lazy1[id] = -1;
        return;
    }
    down(id);
    int mid = (l + r) >> 1;
    update_max(id << 1,l,mid,u,v,val);
    update_max(id << 1 | 1,mid + 1,r,u,v,val);
    st[id] = max(st[id << 1],st[id << 1 | 1]);
}
void update_down(int id,int l,int r,int u,int v,int val)
{
    if(l > v or r < u) return;
    if(u <= l and r <= v)
    {
        st[id] = min(st[id],val);
        if(lazy1[id] != -1)
            lazy1[id] = min(lazy1[id],val);
        else lazy1[id] = val;
        lazy[id] = 0;
        return;
    }
    down(id);
    int mid = (l + r) >> 1;
    update_down(id << 1,l,mid,u,v,val);
    update_down(id << 1 | 1,mid + 1,r,u,v,val);
    st[id] = max(st[id << 1],st[id << 1 | 1]);
}
int get(int id,int l,int r,int u,int v)
{
    if(l > v or r < u) return 0;
    if(u <= l and r <= v) return st[id];
    down(id);
    int mid = (l + r) >> 1;
    return max(get(id << 1,l,mid,u,v),get(id << 1 | 1,mid + 1,r,u,v));
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    memset(lazy1,-1,sizeof lazy1);
    fo(i,0,k - 1)
    {
        if(op[i] == 1) update_max(1,1,n,left[i] + 1,right[i] + 1,height[i]);
        else update_down(1,1,n,left[i] + 1,right[i] + 1,height[i]);
    }
    fo(i,0,n - 1) finalHeight[i] = get(1,1,n,i + 1,i + 1);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Incorrect 2 ms 6492 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 6492 KB Output is correct
2 Correct 101 ms 20052 KB Output is correct
3 Correct 130 ms 13940 KB Output is correct
4 Incorrect 409 ms 26048 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6724 KB Output is correct
3 Incorrect 2 ms 6488 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 6492 KB Output is correct
2 Correct 2 ms 6708 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -