oj.uz

Submission #719838

# Submission time Handle Problem Language Result Execution time Memory
719838 2023-04-06T20:06:12 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 610 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define ff first
#define ss second

const int inf = 1e9;
const int K = 5e5;
const int K1 = 524288;

int amn[2*K1],amx[2*K1];
int pos[K];

void build(int p,int l,int r)
{
    if(l == r)pos[l] = p;
    else
    {
        int m = (l + r) / 2;
        build(p*2,l,m);
        build(p*2+1,m+1,r);
    }
    amn[p] = 0;
    amx[p] = inf;
    return ;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    queue<int> vq[n+1];
    build(1,0,k-1);
    for(int i = 0;i < k;i++)vq[left[i]].push(i);
    for(int i = 0;i < k;i++)vq[right[i]+1].push(i);
    for(int i = 0;i < n;i++)
    {
        while(!vq[i].empty())
        {
            int v = vq[i].front();
            vq[i].pop();
            if(amn[pos[v]] == 0 && amx[pos[v]] == inf)
            {
                if(op[v] == 1)amn[pos[v]] = height[v];
                else amx[pos[v]] = height[v];
            }
            else
            {
                amn[pos[v]] = 0;
                amx[pos[v]] = inf;
            }
            int p = pos[v] / 2;
            while(p != 0)
            {
                int mx = min(amx[p*2],amx[p*2+1]);
                int mn = max(amn[p*2],amn[p*2+1]);
                if(mn > mx)
                {
                    if(mn == amn[p*2+1])mx = mn;
                    else mn = mx;
                }
                amn[p] = mn;
                amx[p] = mx;
                p /= 2;
            }
        }
        finalHeight[i] = amn[1];
    }
    return ;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 8 ms 7380 KB Output is correct
5 Correct 8 ms 7300 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 203 ms 22336 KB Output is correct
3 Correct 169 ms 20768 KB Output is correct
4 Correct 550 ms 86276 KB Output is correct
5 Correct 337 ms 90212 KB Output is correct
6 Correct 345 ms 90348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 8 ms 7252 KB Output is correct
5 Correct 7 ms 7320 KB Output is correct
6 Correct 8 ms 7252 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 210 ms 22528 KB Output is correct
9 Correct 169 ms 20812 KB Output is correct
10 Correct 520 ms 86152 KB Output is correct
11 Correct 340 ms 90284 KB Output is correct
12 Correct 332 ms 90312 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 223 ms 22416 KB Output is correct
15 Correct 31 ms 13132 KB Output is correct
16 Correct 610 ms 86560 KB Output is correct
17 Correct 355 ms 89608 KB Output is correct
18 Correct 374 ms 90148 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 8 ms 7252 KB Output is correct
5 Correct 7 ms 7252 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 203 ms 22416 KB Output is correct
9 Correct 163 ms 20768 KB Output is correct
10 Correct 522 ms 86316 KB Output is correct
11 Correct 333 ms 90256 KB Output is correct
12 Correct 326 ms 90272 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 218 ms 22412 KB Output is correct
15 Correct 32 ms 13020 KB Output is correct
16 Correct 586 ms 86452 KB Output is correct
17 Correct 348 ms 89580 KB Output is correct
18 Correct 355 ms 90212 KB Output is correct
19 Runtime error 247 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -