oj.uz

Submission #138835

# Submission time Handle Problem Language Result Execution time Memory
138835 2019-07-30T12:42:48 Z Runtime_error_ Wall (IOI14_wall) C++14
100 / 100
 1547 ms 69636 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
#define ll long long
using namespace std;
const int inf = 2e6+9,MX = 1e9+9;
int opmin[inf<<2],opmax[inf<<2];

void build(int node,int l,int r){

    opmin[node] = MX;
    opmax[node] = 0;
    if(l == r)
        return;
    build(le,l,mid);
    build(ri,mid+1,r);
}

void tochild(int child,int node){
    opmin[child] = min( opmin[child] , opmin[node] );//If you lower to height h on the child and to
    //height h' on the parent after that, only min(h,h') will take effect

    opmax[child] = max( opmax[child] , opmax[node] );//If you increase to height h on the child and then increase to
    //height h' on the parent, only max(h,h') will take effect

    opmin[child] = max( opmin[child] , opmax[node] );//If you decrease to height h on the child and then increase to
     //height h' on the parent, with h'>h, then the first operation will lose effect
    opmax[child] = min( opmax[child] , opmin[node] );//If you increase to height h on the child and then decrease to
    // height h' on the parent, with h'<h, then the first operation will lose effect.

}

void push(int node,int l,int r){

    if(l == r)
        return ;

    tochild(le,node);
    tochild(ri,node);
    opmax[node] = 0;
    opmin[node] = MX;
}

void update(int node,int l,int r,int x,int y,int val,int type){//type 2 minimize 1 maximize

    push(node,l,r);
    if(l>r || r<x || l>y)
        return ;
    if(l>=x && r<=y){
        if(type == 2)
            opmin[node] = min(opmin[node],val),opmax[node] = min(opmax[node],val);
        else
            opmax[node] = max(opmax[node],val) , opmin[node] = max(opmin[node],val);
        push(node,l,r);
        return ;
    }
    update(le,l,mid,x,y,val,type);
    update(ri,mid+1,r,x,y,val,type);
}

int query(int node,int l,int r,int idx){
    push(node,l,r);
    if(l == r)
        return min(opmin[node],opmax[node]);
    if(idx <= mid)
        return query(le,l,mid,idx);
    return query(ri,mid+1,r,idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    build(1,1,n);
    for(int i=0;i<k;i++)
        update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
    for(int i=1;i<=n;i++)
        finalHeight[i-1] = query(1,1,n,i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 22 ms 888 KB Output is correct
5 Correct 11 ms 888 KB Output is correct
6 Correct 11 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 175 ms 13972 KB Output is correct
3 Correct 267 ms 7984 KB Output is correct
4 Correct 812 ms 20444 KB Output is correct
5 Correct 468 ms 21496 KB Output is correct
6 Correct 458 ms 19892 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 11 ms 888 KB Output is correct
5 Correct 10 ms 860 KB Output is correct
6 Correct 11 ms 860 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 175 ms 13944 KB Output is correct
9 Correct 269 ms 7988 KB Output is correct
10 Correct 846 ms 20420 KB Output is correct
11 Correct 467 ms 21492 KB Output is correct
12 Correct 458 ms 19944 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 193 ms 14124 KB Output is correct
15 Correct 47 ms 2168 KB Output is correct
16 Correct 806 ms 20664 KB Output is correct
17 Correct 466 ms 20332 KB Output is correct
18 Correct 462 ms 20136 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 12 ms 888 KB Output is correct
5 Correct 10 ms 888 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 175 ms 14088 KB Output is correct
9 Correct 267 ms 8056 KB Output is correct
10 Correct 784 ms 20404 KB Output is correct
11 Correct 590 ms 21548 KB Output is correct
12 Correct 457 ms 19960 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 175 ms 14008 KB Output is correct
15 Correct 47 ms 2040 KB Output is correct
16 Correct 793 ms 20728 KB Output is correct
17 Correct 488 ms 20216 KB Output is correct
18 Correct 458 ms 20044 KB Output is correct
19 Correct 1506 ms 69636 KB Output is correct
20 Correct 1500 ms 67192 KB Output is correct
21 Correct 1509 ms 69624 KB Output is correct
22 Correct 1493 ms 67192 KB Output is correct
23 Correct 1547 ms 67136 KB Output is correct
24 Correct 1492 ms 67152 KB Output is correct
25 Correct 1513 ms 67172 KB Output is correct
26 Correct 1511 ms 69596 KB Output is correct
27 Correct 1501 ms 69624 KB Output is correct
28 Correct 1500 ms 67100 KB Output is correct
29 Correct 1497 ms 67184 KB Output is correct
30 Correct 1515 ms 67184 KB Output is correct