oj.uz

Submission #1062940

# Submission time Handle Problem Language Result Execution time Memory
1062940 2024-08-17T12:13:29 Z andrei_iorgulescu Wall (IOI14_wall) C++14
24 / 100
 1218 ms 23444 KB 
#include <bits/stdc++.h>
#include "wall.h"
#warning That's not FB, that's my FB

using namespace std;

vector<int> lol;

struct node
{
    int mx = 0, mx2 = -1, mn = 0, mn2 = -1;
    //bool lazy_tag_max = false, lazy_tag_min = false;
};

node aint[400005];

void prop(int nod, int l, int r)
{
    if (l == r)
        return;
    aint[2 * nod].mx = min(aint[2 * nod].mx, aint[nod].mx);
    aint[2 * nod].mn = min(aint[2 * nod].mn, aint[nod].mx);
    aint[2 * nod].mx = max(aint[2 * nod].mx, aint[nod].mn);
    aint[2 * nod].mn = max(aint[2 * nod].mn, aint[nod].mn);
    aint[2 * nod + 1].mx = min(aint[2 * nod + 1].mx, aint[nod].mx);
    aint[2 * nod + 1].mn = min(aint[2 * nod + 1].mn, aint[nod].mx);
    aint[2 * nod + 1].mx = max(aint[2 * nod + 1].mx, aint[nod].mn);
    aint[2 * nod + 1].mn = max(aint[2 * nod + 1].mn, aint[nod].mn);
}

void update(int nod, int l, int r, int st, int dr, int tip, int h)
{
    if (r < st or dr < l)
        return;
    prop(nod,l,r);
    if (st <= l and r <= dr)
    {
        if (tip == 1)
        {
            if (h <= aint[nod].mn)
                return;
            if (aint[nod].mn2 == -1 or h < aint[nod].mn2)
            {
                if (aint[nod].mx2 == aint[nod].mn)
                    aint[nod].mx2 = h;
                //aint[nod].lazy_tag_min = true;
                aint[nod].mn = h;
                if (aint[nod].mn2 == -1)
                {
                    //aint[nod].lazy_tag_max = true;
                    aint[nod].mx = h;
                }
                //cout << "wow" << nod << ' ' << l << ' ' << r << endl;
                return;
            }
        }
        else
        {
            if (h >= aint[nod].mx)
                return;
            if (aint[nod].mx2 == -1 or h > aint[nod].mx2)
            {
                if (aint[nod].mn2 == aint[nod].mx)
                    aint[nod].mn2 = h;
                //aint[nod].lazy_tag_max = true;
                aint[nod].mx = h;
                if (aint[nod].mx2 == -1)
                {
                    //aint[nod].lazy_tag_min = true;
                    aint[nod].mn = h;
                }
                return;
            }
        }
    }
    //cout << nod << ' ' << l << ' ' << r << endl;
    int mij = (l + r) / 2;
    update(2 * nod, l, mij, st, dr, tip, h);
    update(2 * nod + 1, mij + 1, r, st, dr, tip, h);
    vector<int> ele = {aint[2 * nod].mx, aint[2 * nod].mx2, aint[2 * nod].mn, aint[2 * nod].mn2, aint[2 * nod + 1].mx, aint[2 * nod + 1].mx2, aint[2 * nod + 1].mn, aint[2 * nod + 1].mn2};
    sort(ele.begin(),ele.end());
    vector<int> e2;
    for (int i = 0; i < 8; i++)
        if ((i == 0 or ele[i] != ele[i - 1]) and ele[i] != -1)
            e2.push_back(ele[i]);
    if (e2.size() == 1)
    {
        aint[nod].mx = aint[nod].mn = e2[0];
        aint[nod].mx2 = aint[nod].mn2 = -1;
    }
    else
    {
        int sz = e2.size();
        aint[nod].mx = e2[sz - 1];
        aint[nod].mx2 = e2[sz - 2];
        aint[nod].mn = e2[0];
        aint[nod].mn2 = e2[1];
    }
}

int query(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return 0;
    prop(nod,l,r);
    if (st <= l and r <= dr)
        return aint[nod].mn;
    int mij = (l + r) / 2;
    return max(query(2 * nod,l,mij,st,dr), query(2 * nod + 1,mij + 1,r,st,dr));
}

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; i++)
    {
        left[i]++;
        right[i]++;
        update(1,1,n,left[i],right[i],op[i],height[i]);
    }
    for (int i = 0; i < n; i++)
        finalHeight[i] = query(1,1,n,i + 1,i + 1);
}

///hai sa vedem daca iese si cu beats :)

Compilation message

wall.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 5 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 79 ms 13888 KB Output is correct
3 Correct 448 ms 8556 KB Output is correct
4 Correct 1218 ms 22352 KB Output is correct
5 Correct 681 ms 23444 KB Output is correct
6 Correct 726 ms 22008 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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