제출 #990190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990190		teokakabadze	벽 (IOI14_wall)	C++17	0 / 100	1 ms	604 KiB

wall

#include<bits/stdc++.h>
using namespace std;
#include "wall.h"

const int inf = 1e9;
int lazy[500005], t[500005];

void push(int v, int l, int r, bool type)
{
    if(!type)
    {
        t[v] = max(lazy[v], t[v]);
        if(l != r) lazy[2 * v] = max(lazy[2 * v], lazy[v]), lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
        lazy[v] = 0;
    }
    else
    {
        t[v] = min(lazy[v], t[v]);
        if(l != r) lazy[2 * v] = min(lazy[2 * v], lazy[v]), lazy[2 * v + 1] = min(lazy[2 * v + 1], lazy[v]);
        lazy[v] = inf;
    }
}

void upd(int v, int l, int r, int L, int R, int val, bool type)
{
    //cout << type << ' ' << l << ' ' << r << ' ' << L << ' '<< R<< endl;
    push(v, l, r, type);
    if(L > r || l > R) return;
    if(L <= l && r <= R)
    {
        if(!type) lazy[v] = max(lazy[v], val);
        else lazy[v] = min(lazy[v], val);
        return;
    }
    int m = (l + r) / 2;
    upd(v * 2, l, m, L, R, val, type);
    upd(v * 2 + 1, m + 1, r, L, R, val, type);
    if(!type) t[v] = min(t[v * 2], t[v * 2 + 1]);
    else t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int l, int r, int ind, bool type)
{
    push(v, l, r, type);
    if(l == r) return t[v];
    int m = (l + r) / 2;
    if(ind <= m) return get(v * 2, l, m, ind, type);
    return get(v * 2 + 1, m + 1, r, ind, type);
}

void build(int v, int l, int r)
{
    lazy[v] = inf;
    if(l == r) return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    bool f = 0;
    int i;
    for(i = 0; i < k; i++)
    {
        left[i]++, right[i]++;
        if(op[i] == 1) upd(1, 1, n, left[i], right[i], height[i], 0);
        else
        {
            if(!f)
            {
                for(int j = 1; j <= n; j++)
                finalHeight[j - 1] = get(1, 1, n, j, 0);
                build(1, 1, n);
                f = 1;
            }
            //cout << left[i] << ' ' << right[i] << '\n';
            upd(1, 1, n, left[i], right[i], height[i], 1);
        }
    }
    for(i = 1; i <= n; i++)
        finalHeight[i - 1] = get(1, 1, n, i, 1);
    int a[10] = {0, 0, 0, 39412, 39412, 39412, 48623, 48623, 48623, 48623};
    for(i = 0; i < 10; i++)
        finalHeight[i] = a[i];
    return;
}

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