oj.uz

Submission #1062943

# Submission time Handle Problem Language Result Execution time Memory
1062943 2024-08-17T12:17:15 Z andrei_iorgulescu Wall (IOI14_wall) C++14
61 / 100
 2028 ms 33364 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);

    if (aint[2 * nod].mn == aint[2 * nod].mx)
        aint[2 * nod].mx2 = aint[2 * nod].mn2 = -1;
    else
    {
        aint[2 * nod].mx2 = max(aint[2 * nod].mx2, aint[nod].mn);
        aint[2 * nod].mn2 = min(aint[2 * nod].mn2, aint[nod].mx);
    }
    
    if (aint[2 * nod + 1].mn == aint[2 * nod + 1].mx)
        aint[2 * nod + 1].mx2 = aint[2 * nod + 1].mn2 = -1;
    else
    {
        aint[2 * nod + 1].mx2 = max(aint[2 * nod + 1].mx2, aint[nod].mn);
        aint[2 * nod + 1].mn2 = min(aint[2 * nod + 1].mn2, aint[nod].mx);
    }
}

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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 22 ms 1112 KB Output is correct
5 Correct 16 ms 1116 KB Output is correct
6 Correct 16 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 79 ms 8056 KB Output is correct
3 Correct 453 ms 4760 KB Output is correct
4 Correct 1377 ms 12880 KB Output is correct
5 Correct 731 ms 13400 KB Output is correct
6 Correct 751 ms 13392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 18 ms 1116 KB Output is correct
5 Correct 18 ms 1160 KB Output is correct
6 Correct 16 ms 1116 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 82 ms 13904 KB Output is correct
9 Correct 457 ms 8532 KB Output is correct
10 Correct 1391 ms 22496 KB Output is correct
11 Correct 714 ms 23504 KB Output is correct
12 Correct 790 ms 22096 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 88 ms 14024 KB Output is correct
15 Correct 115 ms 2512 KB Output is correct
16 Correct 2028 ms 22640 KB Output is correct
17 Correct 859 ms 22376 KB Output is correct
18 Correct 907 ms 22196 KB Output is correct

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 Correct 4 ms 348 KB Output is correct
4 Correct 18 ms 1164 KB Output is correct
5 Correct 18 ms 1172 KB Output is correct
6 Correct 16 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 13996 KB Output is correct
9 Correct 457 ms 8548 KB Output is correct
10 Correct 1373 ms 22496 KB Output is correct
11 Correct 719 ms 23380 KB Output is correct
12 Correct 770 ms 21844 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 86 ms 14016 KB Output is correct
15 Correct 102 ms 2528 KB Output is correct
16 Correct 2008 ms 22744 KB Output is correct
17 Correct 850 ms 22172 KB Output is correct
18 Correct 923 ms 22352 KB Output is correct
19 Runtime error 113 ms 33364 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -