oj.uz

Submission #878196

# Submission time Handle Problem Language Result Execution time Memory
878196 2023-11-24T07:05:49 Z JakobZorz Wall (IOI14_wall) C++17
100 / 100
 561 ms 72528 KB 
#include"wall.h"
#include<iostream>
using namespace std;

const int TREE_SIZE=1<<21;

#define upper first
#define lower second

pair<int,int>tree[2*TREE_SIZE];
bool lazy[2*TREE_SIZE];
void update(int node){
    if(node>=TREE_SIZE)
        return;
    
    if(lazy[node]){
        tree[2*node].upper=min(tree[2*node].upper,tree[node].upper);
        tree[2*node].upper=max(tree[2*node].upper,tree[node].lower);
        tree[2*node].lower=min(tree[2*node].lower,tree[node].upper);
        tree[2*node].lower=max(tree[2*node].lower,tree[node].lower);
        
        tree[2*node+1].upper=min(tree[2*node+1].upper,tree[node].upper);
        tree[2*node+1].upper=max(tree[2*node+1].upper,tree[node].lower);
        tree[2*node+1].lower=min(tree[2*node+1].lower,tree[node].upper);
        tree[2*node+1].lower=max(tree[2*node+1].lower,tree[node].lower);
        
        lazy[2*node]=true;
        lazy[2*node+1]=true;
        lazy[node]=false;
    }
}

void lh_bound(int node,int l,int r,int rl,int rr,pair<int,int>bound){
    update(node);
    
    if(r<=rl||rr<=l)
        return;
    
    if(l<=rl&&rr<=r){
        tree[node].lower=max(tree[node].lower,bound.lower);
        tree[node].lower=min(tree[node].lower,bound.upper);
        tree[node].upper=max(tree[node].upper,bound.lower);
        tree[node].upper=min(tree[node].upper,bound.upper);
        
        lazy[node]=true;
        return;
    }
    
    int mid=(rl+rr)/2;
    lh_bound(2*node,l,r,rl,mid,bound);
    lh_bound(2*node+1,l,r,mid,rr,bound);
    
    tree[node].lower=min(tree[2*node].lower,tree[2*node+1].lower);
    tree[node].upper=max(tree[2*node].upper,tree[2*node+1].upper);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    for(int i=0;i<k;i++){
        if(op[i]==1){
            // adding phase
            pair<int,int>bound;
            bound.lower=height[i];
            bound.upper=1000000000;
            lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
        }else{
            // removing phase
            pair<int,int>bound;
            bound.lower=-1000000000;
            bound.upper=height[i];
            lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
        }
    }
    
    for(int i=1;i<2*TREE_SIZE;i++)
        update(i);
    
    for(int i=0;i<n;i++)
        finalHeight[i]=tree[TREE_SIZE+i].lower;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 6 ms 8780 KB Output is correct
3 Correct 5 ms 6488 KB Output is correct
4 Correct 9 ms 9052 KB Output is correct
5 Correct 8 ms 9048 KB Output is correct
6 Correct 7 ms 7000 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 206 ms 22104 KB Output is correct
3 Correct 176 ms 15952 KB Output is correct
4 Correct 485 ms 29968 KB Output is correct
5 Correct 250 ms 26964 KB Output is correct
6 Correct 241 ms 19796 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 6 ms 8804 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 9 ms 9052 KB Output is correct
5 Correct 7 ms 9052 KB Output is correct
6 Correct 7 ms 6988 KB Output is correct
7 Correct 4 ms 8536 KB Output is correct
8 Correct 205 ms 22348 KB Output is correct
9 Correct 182 ms 15956 KB Output is correct
10 Correct 494 ms 30036 KB Output is correct
11 Correct 244 ms 26960 KB Output is correct
12 Correct 240 ms 19756 KB Output is correct
13 Correct 4 ms 8536 KB Output is correct
14 Correct 204 ms 22104 KB Output is correct
15 Correct 31 ms 9820 KB Output is correct
16 Correct 483 ms 30296 KB Output is correct
17 Correct 240 ms 29372 KB Output is correct
18 Correct 250 ms 25680 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 9 ms 9052 KB Output is correct
5 Correct 7 ms 8992 KB Output is correct
6 Correct 7 ms 7004 KB Output is correct
7 Correct 4 ms 8664 KB Output is correct
8 Correct 200 ms 22100 KB Output is correct
9 Correct 182 ms 16012 KB Output is correct
10 Correct 476 ms 29780 KB Output is correct
11 Correct 246 ms 26968 KB Output is correct
12 Correct 239 ms 19760 KB Output is correct
13 Correct 5 ms 8540 KB Output is correct
14 Correct 211 ms 22520 KB Output is correct
15 Correct 31 ms 9916 KB Output is correct
16 Correct 509 ms 30172 KB Output is correct
17 Correct 240 ms 29380 KB Output is correct
18 Correct 240 ms 25684 KB Output is correct
19 Correct 547 ms 71968 KB Output is correct
20 Correct 535 ms 69572 KB Output is correct
21 Correct 552 ms 72376 KB Output is correct
22 Correct 546 ms 69456 KB Output is correct
23 Correct 561 ms 69488 KB Output is correct
24 Correct 537 ms 69808 KB Output is correct
25 Correct 539 ms 69712 KB Output is correct
26 Correct 544 ms 72496 KB Output is correct
27 Correct 541 ms 72528 KB Output is correct
28 Correct 545 ms 69340 KB Output is correct
29 Correct 545 ms 69916 KB Output is correct
30 Correct 544 ms 69844 KB Output is correct