oj.uz

Submission #989995

# Submission time Handle Problem Language Result Execution time Memory
989995 2024-05-29T10:11:47 Z teokakabadze Wall (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);
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -