oj.uz

Submission #719820

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

vector<pair<int,int>> a;
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);
    }
    a[p].ff = 0;
    a[p].ss = inf;
    return ;
}

void change(int p)
{
    if(p == 0)return ;
    int mx = min(a[p*2].ss,a[p*2+1].ss);
    int mn = max(a[p*2].ff,a[p*2+1].ff);
    if(mn > mx)
    {
        if(mn == a[p*2+1].ff)mx = mn;
        else mn = mx;
    }
    a[p].ff = mn;
    a[p].ss = 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];
    int t = 1;
    while(t < k)t *= 2;
    a.resize(t * 2);
    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(a[pos[v]].ff == 0 && a[pos[v]].ss == inf)
            {
                if(op[v] == 1)a[pos[v]].ff = height[v];
                else a[pos[v]].ss = height[v];
            }
            else
            {
                a[pos[v]].ff = 0;
                a[pos[v]].ss = inf;
            }
            change(pos[v] / 2);
        }
        finalHeight[i] = a[1].ff;
    }
    return ;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 9 ms 7252 KB Output is correct
5 Correct 7 ms 7252 KB Output is correct
6 Correct 8 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 187 ms 22424 KB Output is correct
3 Correct 196 ms 20764 KB Output is correct
4 Correct 550 ms 86096 KB Output is correct
5 Correct 306 ms 90272 KB Output is correct
6 Correct 315 ms 90244 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 9 ms 7284 KB Output is correct
6 Correct 9 ms 7252 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 185 ms 22356 KB Output is correct
9 Correct 184 ms 20796 KB Output is correct
10 Correct 583 ms 86168 KB Output is correct
11 Correct 306 ms 90216 KB Output is correct
12 Correct 329 ms 90312 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 213 ms 22536 KB Output is correct
15 Correct 29 ms 13036 KB Output is correct
16 Correct 607 ms 86532 KB Output is correct
17 Correct 338 ms 89736 KB Output is correct
18 Correct 349 ms 90088 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 9 ms 7252 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 8 ms 7252 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 186 ms 22360 KB Output is correct
9 Correct 179 ms 20768 KB Output is correct
10 Correct 500 ms 86092 KB Output is correct
11 Correct 301 ms 90336 KB Output is correct
12 Correct 308 ms 90304 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 203 ms 22348 KB Output is correct
15 Correct 30 ms 13112 KB Output is correct
16 Correct 644 ms 86592 KB Output is correct
17 Correct 321 ms 89580 KB Output is correct
18 Correct 374 ms 90028 KB Output is correct
19 Runtime error 272 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -