제출 #492995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492995		peti1234	벽 (IOI14_wall)	C++17	61 / 100	445 ms	22964 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int c=1<<21, sok=1e9;
int kezd[c], veg[c], kis[c], nagy[c];
int s(int a, int l, int r) {
    if (r<kezd[a] || l>veg[a]) return 0;
    if (l<=kezd[a] && veg[a]<=r) return 2;
    return 1;
}
void push(int a) {
    int x=2*a, y=2*a+1;
    kis[x]=min(nagy[a], max(kis[x], kis[a]));
    nagy[x]=max(kis[a], min(nagy[x], nagy[a]));
    kis[y]=min(nagy[a], max(kis[y], kis[a]));
    nagy[y]=max(kis[a], min(nagy[y], nagy[a]));
    kis[a]=0, nagy[a]=sok;
}
void add(int a, int l, int r, int ert, int f) {
    int p=s(a, l, r);
    if (!p) return;
    if (p==2) {
        if (f==1) {
            kis[a]=max(kis[a], ert);
            nagy[a]=max(nagy[a], ert);
        } else {
            kis[a]=min(kis[a], ert);
            nagy[a]=min(nagy[a], ert);
        }
        return;
    }
    push(a);
    add(2*a, l, r, ert, f), add(2*a+1, l, r, ert, f);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    int po=1;
    while (po<=n) po*=2;
    for (int i=po; i<2*po; i++) {
        kezd[i]=veg[i]=i-po;
        nagy[i]=sok;
    }
    for (int i=po-1; i>=1; i--) {
        kezd[i]=kezd[2*i], veg[i]=veg[2*i+1];
        nagy[i]=sok;
    }
    for (int i=0; i<k; i++) {
        add(1, l[i], r[i], h[i], op[i]);
    }
    for (int i=1; i<po; i++) {
        push(i);
    }
    for (int i=po; i<po+n; i++) {
        ans[i-po]=kis[i];
    }
    return;
}

/*
int main()
{
    ios_base::sync_with_stdio(false);
    return 0;
}
*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39