oj.uz

Submission #969262

# Submission time Handle Problem Language Result Execution time Memory
969262 2024-04-24T20:38:30 Z Hugo1729 Wall (IOI14_wall) C++11
8 / 100
 3000 ms 16044 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int MAXN=4194305;
int sz=1;
int a[MAXN],b[MAXN];//alazy[MAXN],blazy[MAXN];

void push(int v){
    a[2*v]=max(b[v*2],min(a[v],a[2*v]));
    // alazy[2*v]=min(alazy[v],alazy[2*v]);
    a[2*v+1]=max(b[v*2+1],min(a[v],a[2*v+1]));
    // alazy[2*v+1]=min(alazy[v],alazy[2*v+1]);
    // a[v]=alazy[v];

    b[2*v]=min(a[v*2],max(b[v],b[2*v]));
    // blazy[2*v]=max(blazy[v],blazy[2*v]);
    b[2*v+1]=min(a[v*2+1],max(b[v],b[2*v+1]));
    // blazy[2*v+1]=max(blazy[v],blazy[2*v+1]);
    // b[v]=blazy[v];
}

void update1(int v, int tl, int tr, int l, int r, int val){
    // cout << v << ' ' << tl << ' '  << tr << ' ' << l << ' ' << r << ' ' << val << '\n';

    if(l>r)return;
    if(tl==l&&tr==r){
        b[v]=min(a[v],max(b[v],val));
    }else{
        push(v);
        int mid=(tl+tr)/2;
        update1(v*2,tl,mid,l,min(mid,r),val);
        update1(v*2+1,mid+1,tr,max(mid+1,l),r,val);
    }
}

void update2(int v, int tl, int tr, int l, int r, int val){
    // cout << v << ' ' << tl << ' '  << tr << ' ' << l << ' ' << r << ' ' << val << '\n';
    if(l>r)return;
    if(tl==l&&tr==r){
        a[v]=max(b[v],min(a[v],val));
    }else{
        push(v);
        int mid=(tl+tr)/2;
        update2(v*2,tl,mid,l,min(mid,r),val);
        update2(v*2+1,mid+1,tr,max(mid+1,l),r,val);
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    while(sz<n)sz<<=1;

    for(int i=1;i<2*sz;i++){
        a[i]=1000001;
        b[i]=0;
    }

    // cout << "fdas";

    for(int i=k-1;i>=0;i--){
        if(op[i]==1)update1(1,1,sz,left[i]+1,right[i]+1,height[i]);
        else update2(1,1,sz,left[i]+1,right[i]+1,height[i]);

        for(int i=1;i<sz;i++)push(i);
        // cout << height[i];
        // for(int i=0;i<n;i++)cout << '(' << a[i+sz] << ' ' << b[i+sz] << ')';
        // cout << '\n';
    }

    // cout << "adf";

    for(int i=0;i<n;i++)finalHeight[i]=b[i+sz];


    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 6 ms 2396 KB Output is correct
4 Correct 371 ms 2800 KB Output is correct
5 Correct 358 ms 2800 KB Output is correct
6 Correct 377 ms 2796 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 101 ms 15956 KB Output is correct
3 Execution timed out 3070 ms 12532 KB Time limit exceeded
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 2 ms 2584 KB Output is correct
3 Correct 6 ms 2396 KB Output is correct
4 Correct 363 ms 2908 KB Output is correct
5 Correct 376 ms 2652 KB Output is correct
6 Correct 359 ms 2796 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 100 ms 15952 KB Output is correct
9 Execution timed out 3044 ms 13736 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 6 ms 2396 KB Output is correct
4 Correct 362 ms 2800 KB Output is correct
5 Correct 372 ms 2804 KB Output is correct
6 Correct 360 ms 2800 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 101 ms 16044 KB Output is correct
9 Execution timed out 3097 ms 13648 KB Time limit exceeded
10 Halted 0 ms 0 KB -