oj.uz

Submission #719817

# Submission time Handle Problem Language Result Execution time Memory
719817 2023-04-06T18:12:20 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 564 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]].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 4 ms 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 8 ms 7340 KB Output is correct
5 Correct 7 ms 7380 KB Output is correct
6 Correct 7 ms 7380 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 185 ms 29868 KB Output is correct
3 Correct 173 ms 23116 KB Output is correct
4 Correct 533 ms 93640 KB Output is correct
5 Correct 286 ms 97812 KB Output is correct
6 Correct 284 ms 97764 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 468 KB Output is correct
4 Correct 8 ms 7340 KB Output is correct
5 Correct 7 ms 7380 KB Output is correct
6 Correct 8 ms 7396 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 186 ms 29756 KB Output is correct
9 Correct 171 ms 23160 KB Output is correct
10 Correct 513 ms 93556 KB Output is correct
11 Correct 294 ms 97724 KB Output is correct
12 Correct 274 ms 97712 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 199 ms 29872 KB Output is correct
15 Correct 29 ms 13516 KB Output is correct
16 Correct 564 ms 93900 KB Output is correct
17 Correct 324 ms 97544 KB Output is correct
18 Correct 323 ms 97544 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 3 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 8 ms 7320 KB Output is correct
5 Correct 7 ms 7356 KB Output is correct
6 Correct 7 ms 7380 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 176 ms 29816 KB Output is correct
9 Correct 182 ms 23160 KB Output is correct
10 Correct 514 ms 93588 KB Output is correct
11 Correct 289 ms 97720 KB Output is correct
12 Correct 286 ms 97784 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 202 ms 29812 KB Output is correct
15 Correct 31 ms 13584 KB Output is correct
16 Correct 564 ms 93860 KB Output is correct
17 Correct 331 ms 97700 KB Output is correct
18 Correct 318 ms 97484 KB Output is correct
19 Runtime error 257 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -