oj.uz

Submission #719815

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

using namespace std;

#define ll long long
#define mp make_pair
#define ff first
#define ss second

const int inf = 2e9;

vector<pair<int,int>> a;
vector<int> pos;
vector<queue<int>> vq;

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[])
{
    a.resize(k * 4);
    pos.resize(k);
    vq.resize(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(a[pos[v]] == mp(0,inf))
            {
                if(op[v] == 1)a[pos[v]].ff = height[v];
                else a[pos[v]].ss = height[v];
            }
            else a[pos[v]] = mp(0,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 1 ms 212 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7476 KB Output is correct
6 Correct 8 ms 7408 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 175 ms 30108 KB Output is correct
3 Correct 190 ms 23448 KB Output is correct
4 Correct 547 ms 93884 KB Output is correct
5 Correct 284 ms 98080 KB Output is correct
6 Correct 330 ms 98012 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 568 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 7 ms 7476 KB Output is correct
5 Correct 7 ms 7476 KB Output is correct
6 Correct 8 ms 7380 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 172 ms 30028 KB Output is correct
9 Correct 208 ms 23380 KB Output is correct
10 Correct 531 ms 93900 KB Output is correct
11 Correct 305 ms 97964 KB Output is correct
12 Correct 272 ms 97984 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 218 ms 30164 KB Output is correct
15 Correct 30 ms 13836 KB Output is correct
16 Correct 618 ms 94064 KB Output is correct
17 Correct 309 ms 97736 KB Output is correct
18 Correct 340 ms 97824 KB Output is correct

Subtask #4
0 / 39.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 596 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7412 KB Output is correct
6 Correct 7 ms 7380 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 179 ms 30208 KB Output is correct
9 Correct 219 ms 23376 KB Output is correct
10 Correct 523 ms 93884 KB Output is correct
11 Correct 290 ms 97996 KB Output is correct
12 Correct 320 ms 98136 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 195 ms 30092 KB Output is correct
15 Correct 30 ms 13752 KB Output is correct
16 Correct 594 ms 94088 KB Output is correct
17 Correct 348 ms 97684 KB Output is correct
18 Correct 314 ms 97952 KB Output is correct
19 Runtime error 256 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -