oj.uz

답안 #238232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238232 2020-06-10T09:59:00 Z nicolaalexandra 벽 (IOI14_wall) C++14
100 / 100
 835 ms 77536 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define DIM 2000010
#define INF 2000000000
using namespace std;
struct segment_tree{
    int mini,maxi; /// astea sunt lazy urile
} aint[DIM*4];
int sol[DIM];

void update_lazy (int nod, int st, int dr){
    if (st == dr)
        return;
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    aint[fiu_st].maxi = min (aint[fiu_st].maxi,aint[nod].mini);
    aint[fiu_st].mini = min (aint[fiu_st].mini,aint[nod].mini);

    aint[fiu_st].mini = max (aint[fiu_st].mini,aint[nod].maxi);
    aint[fiu_st].maxi = max (aint[fiu_st].maxi,aint[nod].maxi);

    ///
    aint[fiu_dr].maxi = min (aint[fiu_dr].maxi,aint[nod].mini);
    aint[fiu_dr].mini = min (aint[fiu_dr].mini,aint[nod].mini);

    aint[fiu_dr].mini = max (aint[fiu_dr].mini,aint[nod].maxi);
    aint[fiu_dr].maxi = max (aint[fiu_dr].maxi,aint[nod].maxi);

    aint[nod].mini = INF, aint[nod].maxi = 0;
}

void build (int nod, int st, int dr){
    aint[nod] = {INF,0};
    if (st == dr)
        return;

    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
}

void update_maxi (int nod, int st, int dr, int x, int y, int val){
    if (x <= st && dr <= y){
        aint[nod].maxi = max (aint[nod].maxi,val);
        aint[nod].mini = max (aint[nod].mini,val);
        return;
    }
    update_lazy(nod,st,dr);
    int mid = (st+dr)>>1;
    if (x <= mid)
        update_maxi (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update_maxi ((nod<<1)|1,mid+1,dr,x,y,val);

}

void update_mini (int nod, int st, int dr, int x, int y, int val){
    update_lazy(nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].mini = min (aint[nod].mini,val);
        aint[nod].maxi = min (aint[nod].maxi,val);
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        update_mini (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update_mini ((nod<<1)|1,mid+1,dr,x,y,val);
}
void get_elem (int nod, int st, int dr){

    update_lazy (nod,st,dr);

    if (st == dr){
        sol[st] = aint[nod].maxi;
        return;
    }

    int mid = (st+dr)>>1;
    get_elem (nod<<1,st,mid);
    get_elem ((nod<<1)|1,mid+1,dr);
}
void buildWall (int n, int k, int op[], int Left[], int Right[], int v[], int finalHeight[]){

    build (1,0,n-1);
    for (int i=0;i<k;i++){
        if (op[i] == 1)
            update_maxi (1,0,n-1,Left[i],Right[i],v[i]);
        else update_mini (1,0,n-1,Left[i],Right[i],v[i]);
    }

    get_elem(1,0,n-1);

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

}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 221 ms 13944 KB Output is correct
3 Correct 196 ms 8112 KB Output is correct
4 Correct 519 ms 20856 KB Output is correct
5 Correct 339 ms 21880 KB Output is correct
6 Correct 329 ms 20472 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 209 ms 13988 KB Output is correct
9 Correct 195 ms 8184 KB Output is correct
10 Correct 511 ms 20824 KB Output is correct
11 Correct 341 ms 21844 KB Output is correct
12 Correct 332 ms 20344 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 195 ms 14072 KB Output is correct
15 Correct 36 ms 2048 KB Output is correct
16 Correct 524 ms 21088 KB Output is correct
17 Correct 329 ms 20472 KB Output is correct
18 Correct 339 ms 20472 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 211 ms 13944 KB Output is correct
9 Correct 202 ms 8184 KB Output is correct
10 Correct 527 ms 20984 KB Output is correct
11 Correct 336 ms 21880 KB Output is correct
12 Correct 312 ms 20360 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 215 ms 14200 KB Output is correct
15 Correct 35 ms 2048 KB Output is correct
16 Correct 535 ms 21112 KB Output is correct
17 Correct 330 ms 20472 KB Output is correct
18 Correct 334 ms 20472 KB Output is correct
19 Correct 734 ms 77432 KB Output is correct
20 Correct 777 ms 75000 KB Output is correct
21 Correct 763 ms 77536 KB Output is correct
22 Correct 760 ms 74872 KB Output is correct
23 Correct 793 ms 75004 KB Output is correct
24 Correct 787 ms 75000 KB Output is correct
25 Correct 835 ms 75104 KB Output is correct
26 Correct 818 ms 77340 KB Output is correct
27 Correct 825 ms 77472 KB Output is correct
28 Correct 800 ms 74956 KB Output is correct
29 Correct 831 ms 74924 KB Output is correct
30 Correct 794 ms 74928 KB Output is correct