oj.uz

답안 #1104202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104202 2024-10-23T08:49:14 Z tammaidai 벽 (IOI14_wall) C++17
100 / 100
 601 ms 69352 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

# 결과 실행 시간 메모리 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 716 KB Output is correct
5 Correct 5 ms 1104 KB Output is correct
6 Correct 5 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 93 ms 11336 KB Output is correct
3 Correct 135 ms 8008 KB Output is correct
4 Correct 390 ms 16968 KB Output is correct
5 Correct 254 ms 20552 KB Output is correct
6 Correct 245 ms 18000 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 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 4 ms 908 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 90 ms 8172 KB Output is correct
9 Correct 132 ms 8104 KB Output is correct
10 Correct 385 ms 10824 KB Output is correct
11 Correct 253 ms 12444 KB Output is correct
12 Correct 252 ms 18128 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 99 ms 13764 KB Output is correct
15 Correct 22 ms 2128 KB Output is correct
16 Correct 382 ms 18760 KB Output is correct
17 Correct 252 ms 19528 KB Output is correct
18 Correct 245 ms 19244 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 5 ms 848 KB Output is correct
5 Correct 5 ms 904 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 96 ms 12872 KB Output is correct
9 Correct 136 ms 8008 KB Output is correct
10 Correct 368 ms 17988 KB Output is correct
11 Correct 234 ms 16728 KB Output is correct
12 Correct 224 ms 19792 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 85 ms 13604 KB Output is correct
15 Correct 21 ms 2128 KB Output is correct
16 Correct 368 ms 20048 KB Output is correct
17 Correct 241 ms 19784 KB Output is correct
18 Correct 226 ms 19528 KB Output is correct
19 Correct 552 ms 69352 KB Output is correct
20 Correct 594 ms 66888 KB Output is correct
21 Correct 599 ms 69192 KB Output is correct
22 Correct 586 ms 67064 KB Output is correct
23 Correct 577 ms 66116 KB Output is correct
24 Correct 591 ms 67144 KB Output is correct
25 Correct 600 ms 67132 KB Output is correct
26 Correct 581 ms 69164 KB Output is correct
27 Correct 601 ms 68676 KB Output is correct
28 Correct 600 ms 66120 KB Output is correct
29 Correct 580 ms 65352 KB Output is correct
30 Correct 522 ms 66768 KB Output is correct