oj.uz

Submission #719837

# Submission time Handle Problem Language Result Execution time Memory
719837 2023-04-06T20:03:18 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 622 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 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 564 KB Output is correct
4 Correct 7 ms 7316 KB Output is correct
5 Correct 11 ms 7252 KB Output is correct
6 Correct 9 ms 7340 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 203 ms 22296 KB Output is correct
3 Correct 168 ms 20748 KB Output is correct
4 Correct 543 ms 86136 KB Output is correct
5 Correct 334 ms 90368 KB Output is correct
6 Correct 332 ms 90580 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 1 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 8 ms 7316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 191 ms 22416 KB Output is correct
9 Correct 200 ms 20780 KB Output is correct
10 Correct 561 ms 86104 KB Output is correct
11 Correct 347 ms 90464 KB Output is correct
12 Correct 343 ms 90344 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 246 ms 22412 KB Output is correct
15 Correct 30 ms 13128 KB Output is correct
16 Correct 622 ms 86380 KB Output is correct
17 Correct 355 ms 89676 KB Output is correct
18 Correct 361 ms 90236 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 228 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 7 ms 7252 KB Output is correct
5 Correct 9 ms 7252 KB Output is correct
6 Correct 12 ms 7252 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 197 ms 22304 KB Output is correct
9 Correct 169 ms 20816 KB Output is correct
10 Correct 526 ms 86132 KB Output is correct
11 Correct 355 ms 90280 KB Output is correct
12 Correct 340 ms 90272 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 209 ms 22476 KB Output is correct
15 Correct 29 ms 13120 KB Output is correct
16 Correct 610 ms 86532 KB Output is correct
17 Correct 361 ms 89548 KB Output is correct
18 Correct 382 ms 90116 KB Output is correct
19 Runtime error 262 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -