oj.uz

Submission #1103990

# Submission time Handle Problem Language Result Execution time Memory
1103990 2024-10-22T14:28:34 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 623 ms 62280 KB 
#include "wall.h"
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2000000;
pair<int,int> seg[4*N+7];

void push(int l,int r,int node){
    if(l==r) return ;
    int ll=node*2;
    int rr=node*2+1;
    seg[ll].first = min(seg[ll].first, seg[node].first);
    seg[ll].first = max(seg[ll].first, seg[node].second);
    seg[ll].second = min(seg[ll].second, seg[node].first);
    seg[ll].second = max(seg[ll].second, seg[node].second);
    seg[rr].first = min(seg[rr].first, seg[node].first);
    seg[rr].first = max(seg[rr].first, seg[node].second);
    seg[rr].second = min(seg[rr].second, seg[node].first);
    seg[rr].second = max(seg[rr].second, seg[node].second);
}

void update(int l,int r,int idx1,int idx2,int val,int node,int mode){
    push(l,r,node);
    if(l>idx2 || r<idx1) return ;
    if(l>=idx1 && r<=idx2){
        if(mode){
            seg[node].first=min(seg[node].first,val);
            seg[node].second=min(seg[node].second,val);
        }
        else{
            seg[node].first=max(seg[node].first,val);
            seg[node].second=max(seg[node].second,val);
        }
        return ;
    }
    seg[node].first=1e9;
    seg[node].second=-1e9;
    int mid=(l+r)>>1;
    update(l,mid,idx1,idx2,val,node*2,mode);
    update(mid+1,r,idx1,idx2,val,node*2+1,mode);
}

void query(int l,int r,int node, int arr[]){
    if(l==r){
        arr[l-1]=seg[node].first;
        return ;
    }
    push(l,r,node);
    int mid=(l+r)>>1;
    query(l,mid,node*2,arr);
    query(mid+1,r,node*2+1,arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; ++i) {
        update(1,n,left[i]+1,right[i]+1,height[i],1,op[i]-1);
    }
    query(1,n,1,finalHeight);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 8 ms 848 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 105 ms 8076 KB Output is correct
3 Correct 147 ms 4420 KB Output is correct
4 Correct 403 ms 10824 KB Output is correct
5 Correct 267 ms 11240 KB Output is correct
6 Correct 242 ms 11848 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 5 ms 848 KB Output is correct
6 Correct 5 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 89 ms 8264 KB Output is correct
9 Correct 134 ms 4200 KB Output is correct
10 Correct 359 ms 10824 KB Output is correct
11 Correct 248 ms 11336 KB Output is correct
12 Correct 230 ms 11848 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 82 ms 8520 KB Output is correct
15 Correct 20 ms 1360 KB Output is correct
16 Correct 364 ms 11100 KB Output is correct
17 Correct 237 ms 13640 KB Output is correct
18 Correct 224 ms 11668 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 4 ms 812 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 80 ms 8196 KB Output is correct
9 Correct 132 ms 6472 KB Output is correct
10 Correct 363 ms 11336 KB Output is correct
11 Correct 236 ms 11336 KB Output is correct
12 Correct 229 ms 11352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 94 ms 8548 KB Output is correct
15 Correct 22 ms 1872 KB Output is correct
16 Correct 358 ms 11080 KB Output is correct
17 Correct 249 ms 13452 KB Output is correct
18 Correct 248 ms 11080 KB Output is correct
19 Correct 571 ms 59228 KB Output is correct
20 Correct 538 ms 56656 KB Output is correct
21 Correct 556 ms 62280 KB Output is correct
22 Correct 547 ms 56484 KB Output is correct
23 Correct 546 ms 56648 KB Output is correct
24 Correct 565 ms 56600 KB Output is correct
25 Correct 570 ms 56512 KB Output is correct
26 Correct 623 ms 59208 KB Output is correct
27 Correct 565 ms 59208 KB Output is correct
28 Correct 528 ms 56676 KB Output is correct
29 Correct 523 ms 56724 KB Output is correct
30 Correct 525 ms 56504 KB Output is correct