oj.uz

Submission #719822

# Submission time Handle Problem Language Result Execution time Memory
719822 2023-04-06T18:41:03 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 538 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;

int amn[4*K],amx[4*K];
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 change(int p)
{
    if(p == 0)return ;
    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;
    change(p / 2);
    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;
            }
            change(pos[v] / 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 7316 KB Output is correct
5 Correct 7 ms 7252 KB Output is correct
6 Correct 7 ms 7336 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 161 ms 22372 KB Output is correct
3 Correct 163 ms 20900 KB Output is correct
4 Correct 506 ms 86216 KB Output is correct
5 Correct 272 ms 90352 KB Output is correct
6 Correct 253 ms 90404 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 8 ms 7316 KB Output is correct
5 Correct 7 ms 7320 KB Output is correct
6 Correct 7 ms 7332 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 164 ms 22432 KB Output is correct
9 Correct 160 ms 20812 KB Output is correct
10 Correct 489 ms 86144 KB Output is correct
11 Correct 268 ms 90312 KB Output is correct
12 Correct 251 ms 90320 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 184 ms 22408 KB Output is correct
15 Correct 28 ms 13040 KB Output is correct
16 Correct 538 ms 86472 KB Output is correct
17 Correct 302 ms 89596 KB Output is correct
18 Correct 303 ms 90092 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 1 ms 468 KB Output is correct
4 Correct 8 ms 7316 KB Output is correct
5 Correct 8 ms 7356 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 163 ms 22432 KB Output is correct
9 Correct 158 ms 20812 KB Output is correct
10 Correct 473 ms 86116 KB Output is correct
11 Correct 269 ms 90284 KB Output is correct
12 Correct 252 ms 90328 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 185 ms 22408 KB Output is correct
15 Correct 28 ms 13140 KB Output is correct
16 Correct 537 ms 86496 KB Output is correct
17 Correct 300 ms 89756 KB Output is correct
18 Correct 298 ms 90144 KB Output is correct
19 Runtime error 233 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -