oj.uz

답안 #990192

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990192 2024-05-29T20:19:39 Z teokakabadze 벽 (IOI14_wall) C++17
0 / 100
 1 ms 348 KB 
#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);
    for(i = 1; i <= n; i++)
    for(int j = 0; j < k; j++)
    {
        if(i >= left[j] && i <= right[j])
        {
            if(op[j] == 1) finalHeight[i] = max(finalHeight[i], height[j]);
            else finalHeight[i] = min(finalHeight[i], height[j]);
        }
    }
    return;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -