oj.uz

Submission #337734

# Submission time Handle Problem Language Result Execution time Memory
337734 2020-12-21T12:55:32 Z blue Wall (IOI14_wall) C++11
100 / 100
 1394 ms 183020 KB 
#include "wall.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//Maintain a set of updates, update it at left and right points of every update
//Sort the updates by index
//Segtree over update indices
//
// void q(int i)
// {
//     cout << i << '\n';
// }

struct segtree
{
    int l;
    int r;

    int mn;
    int mx;

    segtree* left;
    segtree* right;

    segtree();

    segtree(int L, int R);

    void enable(int i, int op, int height);

    void disable(int i);

    int rangemin(int L, int R);

    int rangemax(int L, int R);

    void printmax();

    void printmin();

    int binary_search(int suffixMin, int suffixMax);
};

vector<int> enable[2000000];
vector<int> disable[2000000];

segtree V[1000000];
int vcount = -1;

segtree::segtree()
{
    mn = 1e5 + 1;
    mx = 0;
}

segtree::segtree(int L, int R)
{
    l = L;
    r = R;

    mn = 1e5 + 1;
    mx = 0;

    if(l == r) return;
    int m = (l+r+2)/2 - 1; //for -1
    vcount++;
    left = &V[vcount];
    *left = segtree(l, m);
    vcount++;
    right = &V[vcount];
    *right = segtree(m+1, r);
}

void segtree::enable(int i, int op, int height)
{
    if(i < l || r < i) return;

    if(op == 1)
    {
        if(l == r) mx = height;
        else
        {
            left->enable(i, 1, height);
            right->enable(i, 1, height);

            mx = max(left->mx, right->mx);
        }
    }
    else
    {
        if(l == r) mn = height;
        else
        {
            left->enable(i, 2, height);
            right->enable(i, 2, height);

            mn = min(left->mn, right->mn);
        }
    }
}

void segtree::disable(int i)
{
    if(i < l || r < i) return;

    if(l == r)
    {
        mn = 1e5+1;
        mx = 0;
    }
    else
    {
        left->disable(i);
        right->disable(i);

        mx = max(left->mx, right->mx);
        mn = min(left->mn, right->mn);
    }
}

int segtree::rangemin(int L, int R)
{
    if(R < l || r < L) return 1e5+1;
    if(L <= l && r <= R)
    {
        return mn;
    }
    return min(left->rangemin(L, R), right->rangemin(L, R));
}

int segtree::rangemax(int L, int R)
{
    if(R < l || r < L) return 0;
    if(L <= l && r <= R) return mx;
    return max(left->rangemax(L, R), right->rangemax(L, R));
}

void segtree::printmax()
{
    if(left == NULL) cout << mx << ' ';
    else
    {
        left->printmax();
        right->printmax();
    }
}

void segtree::printmin()
{
    if(left == NULL) cout << mn << ' ';
    else
    {
        left->printmin();
        right->printmin();
    }
}

int segtree::binary_search(int suffixMin = 1e5+1, int suffixMax = 0) {
    // cout << "search " << a << ' ' << b << '\n';
    if(l == r)
    {
        if (mn == 1e5+1)
            return min(suffixMin, mn);
        else
            return max(suffixMax, mx);
    }
    int m = (l+r+2)/2-1;
    if (min(suffixMin, right->mn) <= max(suffixMax, right->mx))
        return right->binary_search(suffixMin, suffixMax);
    else
        return left->binary_search(
            min(suffixMin, right->mn), max(suffixMax, right->mx));
}


segtree* T;
int N;
int K;

                            //1 = max, 2 = min
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    N = n;
    K = k;
    segtree S(-1, k-1);
    S.enable(-1, 2, 0);

    T = &S;

    for(int j = 0; j < k; j++)
    {
        enable[left[j]].push_back(j);
        disable[right[j]].push_back(j);
    }

    int temp = 0;

    for(int i = 0; i < n; i++)
    {
        // cout << "i = " << i << '\n';


        for(int j: enable[i])
        {
            S.enable(j, op[j], height[j]);
            // cout << "enable " << j << '\n';

            // S.printmax();
            // cout << '\n';
            // S.printmin();
            // cout << '\n';

        }
        if(enable[i].size() != 0 || (i > 0 && disable[i-1].size() != 0))
        {

            temp = T->binary_search();
            // cout << temp << '\n';
            // cout << "\n\n\n";
        }
        for(int j: disable[i])
        {
             S.disable(j);
            // cout << "disable " << j << '\n';

            // S.printmax();
            // cout << '\n';
            // S.printmin();
            // cout << "\n\n\n";

        }

        finalHeight[i] = temp;
    }
}

Compilation message

wall.cpp: In member function 'int segtree::binary_search(int, int)':
wall.cpp:169:9: warning: unused variable 'm' [-Wunused-variable]
  169 |     int m = (l+r+2)/2-1;
      |         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 125548 KB Output is correct
2 Correct 84 ms 125804 KB Output is correct
3 Correct 82 ms 125676 KB Output is correct
4 Correct 87 ms 126060 KB Output is correct
5 Correct 88 ms 126060 KB Output is correct
6 Correct 87 ms 126060 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 125548 KB Output is correct
2 Correct 490 ms 141008 KB Output is correct
3 Correct 486 ms 135764 KB Output is correct
4 Correct 1380 ms 146884 KB Output is correct
5 Correct 552 ms 145260 KB Output is correct
6 Correct 543 ms 145004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 125548 KB Output is correct
2 Correct 97 ms 125932 KB Output is correct
3 Correct 91 ms 125676 KB Output is correct
4 Correct 89 ms 126188 KB Output is correct
5 Correct 87 ms 126044 KB Output is correct
6 Correct 87 ms 126060 KB Output is correct
7 Correct 81 ms 125548 KB Output is correct
8 Correct 552 ms 141008 KB Output is correct
9 Correct 476 ms 135660 KB Output is correct
10 Correct 1365 ms 147052 KB Output is correct
11 Correct 579 ms 145288 KB Output is correct
12 Correct 545 ms 145004 KB Output is correct
13 Correct 81 ms 125676 KB Output is correct
14 Correct 496 ms 141008 KB Output is correct
15 Correct 129 ms 127596 KB Output is correct
16 Correct 1394 ms 147120 KB Output is correct
17 Correct 553 ms 144816 KB Output is correct
18 Correct 586 ms 144596 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125524 KB Output is correct
2 Correct 85 ms 125804 KB Output is correct
3 Correct 82 ms 125676 KB Output is correct
4 Correct 87 ms 126188 KB Output is correct
5 Correct 87 ms 126056 KB Output is correct
6 Correct 89 ms 126060 KB Output is correct
7 Correct 81 ms 125548 KB Output is correct
8 Correct 490 ms 141008 KB Output is correct
9 Correct 471 ms 135872 KB Output is correct
10 Correct 1332 ms 147052 KB Output is correct
11 Correct 557 ms 145388 KB Output is correct
12 Correct 555 ms 145004 KB Output is correct
13 Correct 81 ms 125548 KB Output is correct
14 Correct 495 ms 141136 KB Output is correct
15 Correct 122 ms 127596 KB Output is correct
16 Correct 1371 ms 147368 KB Output is correct
17 Correct 549 ms 144748 KB Output is correct
18 Correct 551 ms 144492 KB Output is correct
19 Correct 879 ms 178540 KB Output is correct
20 Correct 870 ms 176108 KB Output is correct
21 Correct 887 ms 178540 KB Output is correct
22 Correct 864 ms 176236 KB Output is correct
23 Correct 872 ms 176108 KB Output is correct
24 Correct 876 ms 176056 KB Output is correct
25 Correct 878 ms 176108 KB Output is correct
26 Correct 875 ms 178668 KB Output is correct
27 Correct 870 ms 178796 KB Output is correct
28 Correct 871 ms 175980 KB Output is correct
29 Correct 874 ms 183020 KB Output is correct
30 Correct 869 ms 183020 KB Output is correct