oj.uz

Submission #290299

# Submission time Handle Problem Language Result Execution time Memory
290299 2020-09-03T15:35:53 Z AaronNaidu Wall (IOI14_wall) C++14
24 / 100
 380 ms 21624 KB 
#include <bits/stdc++.h>
using namespace std;

const int pow2 = 131072;

int segTree[2*pow2];
//pair<int, int> lazyMin[2*pow2];
//pair<int, int> lazyMax[2*pow2];
int lazyUpdate[2*pow2];
int lazyMin[2*pow2];

set<pair<pair<int, int>, int> > s;

void setMax(int node, int nodeStart, int nodeEnd, int rangeStart, int rangeEnd, int amount) {
    if (nodeStart > rangeEnd or nodeEnd < rangeStart)
    {
        return;
    }
    /*if (node >= pow2)
    {
        if (lazyUpdate[node] != -1)
        {             
            segTree[node] = max(lazyUpdate[node], segTree[node]);
            lazyUpdate[node] = -1;
        }
        segTree[node] = max(amount, segTree[node]);
        return;
    }
    if (lazyUpdate[node] != -1)
    {
        //segTree[node] = max(lazyUpdate[node], segTree[node]);
        lazyUpdate[2*node] = max(lazyUpdate[2*node], lazyUpdate[node]);
        lazyUpdate[2*node+1] = max(lazyUpdate[2*node+1], lazyUpdate[node]);
    }*/
    if (nodeStart >= rangeStart and nodeEnd <= rangeEnd)
    {
        lazyUpdate[node] = max(lazyUpdate[node], amount);
        return;
    }
    int med = (nodeStart + nodeEnd)/2;
    setMax(2*node, nodeStart, med, rangeStart, rangeEnd, amount);
    setMax(2*node+1, med+1, nodeEnd, rangeStart, rangeEnd, amount);
}

void setMin(int node, int nodeStart, int nodeEnd, int rangeStart, int rangeEnd, int amount) {
    if (nodeStart > rangeEnd or nodeEnd < rangeStart)
    {
        return;
    }
    /*if (node >= pow2)
    {
        if (lazyUpdate[node] != -1)
        {             
            segTree[node] = max(lazyUpdate[node], segTree[node]);
            lazyUpdate[node] = -1;
        }
        segTree[node] = max(amount, segTree[node]);
        return;
    }
    if (lazyUpdate[node] != -1)
    {
        //segTree[node] = max(lazyUpdate[node], segTree[node]);
        lazyUpdate[2*node] = max(lazyUpdate[2*node], lazyUpdate[node]);
        lazyUpdate[2*node+1] = max(lazyUpdate[2*node+1], lazyUpdate[node]);
    }*/
    if (nodeStart >= rangeStart and nodeEnd <= rangeEnd)
    {
        lazyMin[node] = min(lazyMin[node], amount);
        return;
    }
    int med = (nodeStart + nodeEnd)/2;
    setMin(2*node, nodeStart, med, rangeStart, rangeEnd, amount);
    setMin(2*node+1, med+1, nodeEnd, rangeStart, rangeEnd, amount);
}

void buildWall(int n, int k, int op[],int left[],int right[],int heights[],int finalHeight[]) {
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = 0;
    }
    int turningPoint = k;
    for (int i = 0; i < k; i++)
    {
        if (op[i] == 2)
        {
            turningPoint = i;
            break;
        }
    }
    for (int i = 0; i < 2*pow2; i++)
    {
        lazyUpdate[i] = 0;
        lazyMin[i] = 1000000007;
    }

    for (int i = 0; i < turningPoint; i++)
    {
        setMax(1, 0, pow2-1, left[i], right[i], heights[i]);
    }
    for (int i = turningPoint; i < k; i++)
    {
        setMin(1, 0, pow2-1, left[i], right[i], heights[i]);
    }
    for (int i = 1; i < 2*pow2; i++)
    {
        lazyUpdate[i] = max(lazyUpdate[i], lazyUpdate[i/2]);
        lazyMin[i] = min(lazyMin[i], lazyMin[i/2]);
    }
    for (int i = 0; i < n; i++)
    {
        if (lazyMin[i+pow2] == 1000000007)
        {
            finalHeight[i] = lazyUpdate[i+pow2];
        }
        else
        {
            finalHeight[i] = min(lazyMin[i+pow2], lazyUpdate[i+pow2]);
        }
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2432 KB Output is correct
2 Correct 231 ms 10232 KB Output is correct
3 Correct 148 ms 5752 KB Output is correct
4 Correct 380 ms 10876 KB Output is correct
5 Correct 270 ms 21624 KB Output is correct
6 Correct 258 ms 19916 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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