oj.uz

Submission #373199

# Submission time Handle Problem Language Result Execution time Memory
373199 2021-03-03T17:38:23 Z Doxeno Wall (IOI14_wall) C++17
24 / 100
 607 ms 38380 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2097152;
int m[2*MAXN], mx[2*MAXN],h[2*MAXN],t[2*MAXN],lz[MAXN*2];

void push_down(int pos){
    if(pos >= MAXN || lz[pos] == 0)return;
    lz[pos] = 0; lz[pos*2] = lz[pos*2+1] = 1;
    t[pos*2] = t[pos*2+1] = t[pos];
    if(m[pos*2] > mx[pos])t[pos*2] = 1;
    if(m[pos*2+1] > mx[pos])t[pos*2+1] = 1;
    mx[pos*2] = min(mx[pos*2],mx[pos]);
    mx[pos*2+1] = min(mx[pos*2+1],mx[pos]);
    m[pos*2] = max(m[pos*2],m[pos]);
    m[pos*2+1] = max(m[pos*2+1],m[pos]);
}

void upx(int l, int r, int ql, int qr, int n, int val){
    if(l >= qr || r <= ql)return;
    if(l >= ql && r <= qr){
        if(val < m[n])t[n]=1;
        mx[n] = min(mx[n],val);
        m[n] = min(m[n],val);
        lz[n] = 1;
        return;
    }
    push_down(n);
    upx(l,(l+r)/2,ql,qr,2*n,val);
    upx((l+r)/2,r,ql,qr,2*n+1,val);
}

void upm(int l, int r, int ql, int qr, int n, int val){
    if(l >= qr || r <= ql)return;
    if(l >= ql && r <= qr){
        mx[n] = max(mx[n],val);
        m[n] = max(m[n],val);
        lz[n] = 1;
        return;
    }
    push_down(n);
    upm(l,(l+r)/2,ql,qr,2*n,val);
    upm((l+r)/2,r,ql,qr,2*n+1,val);
}


void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
    for(int i = 0; i < MAXN*2; i++)mx[i] = 1000000000;
    for(int i = 0; i < k; i++){
        if(op[i] == 1)upm(0,MAXN,left[i],right[i]+1,1,height[i]);
        else upx(0,MAXN,left[i],right[i]+1,1,height[i]);
    }
    for(int i = 1; i < MAXN; i++)push_down(i);
    for(int i = 0; i < n; i++){
    //    cout << mx[MAXN+i] << " " << m[MAXN+i]<<endl;
        finalHeight[i] = t[MAXN+i]?mx[MAXN+i]:m[MAXN+i];
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16876 KB Output is correct
2 Correct 258 ms 30712 KB Output is correct
3 Correct 222 ms 24556 KB Output is correct
4 Correct 607 ms 37356 KB Output is correct
5 Correct 302 ms 38380 KB Output is correct
6 Correct 293 ms 36844 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16748 KB Output is correct
2 Correct 18 ms 16876 KB Output is correct
3 Incorrect 18 ms 17004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16748 KB Output is correct
2 Correct 18 ms 16876 KB Output is correct
3 Incorrect 17 ms 17004 KB Output isn't correct
4 Halted 0 ms 0 KB -