Submission #990193

#	Time	Username	Problem	Language	Result	Execution time	Memory
990193		teokakabadze	Wall (IOI14_wall)	C++17	8 / 100	3074 ms	8272 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); */
    for(i = 0; 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;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:62:10: warning: unused variable 'f' [-Wunused-variable]
   62 |     bool f = 0;
      |          ^

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