oj.uz

Submission #719794

# Submission time Handle Problem Language Result Execution time Memory
719794 2023-04-06T17:18:27 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 594 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] = mp(0,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] = mp(mn,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 0 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 7380 KB Output is correct
5 Correct 8 ms 7380 KB Output is correct
6 Correct 8 ms 7380 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 188 ms 29816 KB Output is correct
3 Correct 188 ms 26948 KB Output is correct
4 Correct 521 ms 103344 KB Output is correct
5 Correct 310 ms 107920 KB Output is correct
6 Correct 304 ms 106464 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 3 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 9 ms 7480 KB Output is correct
5 Correct 8 ms 7412 KB Output is correct
6 Correct 7 ms 7476 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 195 ms 35616 KB Output is correct
9 Correct 191 ms 26912 KB Output is correct
10 Correct 539 ms 103524 KB Output is correct
11 Correct 299 ms 107952 KB Output is correct
12 Correct 293 ms 106296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 219 ms 35600 KB Output is correct
15 Correct 30 ms 14132 KB Output is correct
16 Correct 576 ms 103508 KB Output is correct
17 Correct 328 ms 106564 KB Output is correct
18 Correct 337 ms 106608 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 572 KB Output is correct
4 Correct 8 ms 7380 KB Output is correct
5 Correct 7 ms 7416 KB Output is correct
6 Correct 7 ms 7380 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 193 ms 35676 KB Output is correct
9 Correct 176 ms 26976 KB Output is correct
10 Correct 540 ms 103528 KB Output is correct
11 Correct 313 ms 107916 KB Output is correct
12 Correct 303 ms 106320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 213 ms 35632 KB Output is correct
15 Correct 29 ms 14140 KB Output is correct
16 Correct 594 ms 103520 KB Output is correct
17 Correct 336 ms 106548 KB Output is correct
18 Correct 351 ms 106560 KB Output is correct
19 Runtime error 320 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -