oj.uz

Submission #719816

# Submission time Handle Problem Language Result Execution time Memory
719816 2023-04-06T18:02:06 Z ovidiush11 Wall (IOI14_wall) C++14
61 / 100
 611 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);
    }
    if(l > r)
    {
        cout<<-1;
        return;
    }
    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 0 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 7 ms 7380 KB Output is correct
5 Correct 7 ms 7360 KB Output is correct
6 Correct 8 ms 7300 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 185 ms 29864 KB Output is correct
3 Correct 206 ms 23224 KB Output is correct
4 Correct 518 ms 93852 KB Output is correct
5 Correct 313 ms 97744 KB Output is correct
6 Correct 282 ms 97740 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 596 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 8 ms 7380 KB Output is correct
5 Correct 7 ms 7380 KB Output is correct
6 Correct 7 ms 7380 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 184 ms 29772 KB Output is correct
9 Correct 168 ms 23252 KB Output is correct
10 Correct 522 ms 93728 KB Output is correct
11 Correct 296 ms 97868 KB Output is correct
12 Correct 289 ms 97740 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 215 ms 29864 KB Output is correct
15 Correct 31 ms 13612 KB Output is correct
16 Correct 611 ms 93860 KB Output is correct
17 Correct 322 ms 97556 KB Output is correct
18 Correct 326 ms 97500 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 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 8 ms 7336 KB Output is correct
5 Correct 7 ms 7352 KB Output is correct
6 Correct 7 ms 7380 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 188 ms 29760 KB Output is correct
9 Correct 166 ms 23112 KB Output is correct
10 Correct 497 ms 93540 KB Output is correct
11 Correct 296 ms 97792 KB Output is correct
12 Correct 283 ms 97716 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 214 ms 29904 KB Output is correct
15 Correct 29 ms 13568 KB Output is correct
16 Correct 590 ms 93940 KB Output is correct
17 Correct 335 ms 97740 KB Output is correct
18 Correct 326 ms 97640 KB Output is correct
19 Runtime error 277 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -