oj.uz

Submission #719839

# Submission time Handle Problem Language Result Execution time Memory
719839 2023-04-06T20:13:15 Z ovidiush11 Wall (IOI14_wall) C++14
100 / 100
 604 ms 47048 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;
const int K1 = 524288;

int amn[2*K1],amx[2*K1];
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);
    }
    amn[p] = 0;
    amx[p] = inf;
    return ;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    vector<pair<int,int>> vs;
    int id = 0;
    build(1,0,k-1);
    for(int i = 0;i < k;i++)vs.push_back(make_pair(left[i],i));
    for(int i = 0;i < k;i++)vs.push_back(make_pair(right[i]+1,i));
    sort(vs.begin(),vs.end());
    for(int i = 0;i < n;i++)
    {
        while(vs[id].ff == i)
        {
            int v = vs[id].ss;
            id++;
            if(amn[pos[v]] == 0 && amx[pos[v]] == inf)
            {
                if(op[v] == 1)amn[pos[v]] = height[v];
                else amx[pos[v]] = height[v];
            }
            else
            {
                amn[pos[v]] = 0;
                amx[pos[v]] = inf;
            }
            int p = pos[v] / 2;
            while(p != 0)
            {
                int mx = min(amx[p*2],amx[p*2+1]);
                int mn = max(amn[p*2],amn[p*2+1]);
                if(mn > mx)
                {
                    if(mn == amn[p*2+1])mx = mn;
                    else mn = mx;
                }
                amn[p] = mn;
                amx[p] = mx;
                p /= 2;
            }
        }
        finalHeight[i] = amn[1];
    }
    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 724 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 772 KB Output is correct
5 Correct 6 ms 720 KB Output is correct
6 Correct 4 ms 772 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 246 ms 26540 KB Output is correct
3 Correct 197 ms 12740 KB Output is correct
4 Correct 555 ms 26680 KB Output is correct
5 Correct 369 ms 26628 KB Output is correct
6 Correct 361 ms 26688 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 4 ms 696 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 756 KB Output is correct
5 Correct 5 ms 772 KB Output is correct
6 Correct 4 ms 772 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 239 ms 26556 KB Output is correct
9 Correct 185 ms 12764 KB Output is correct
10 Correct 539 ms 26736 KB Output is correct
11 Correct 375 ms 26552 KB Output is correct
12 Correct 370 ms 26604 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 245 ms 26604 KB Output is correct
15 Correct 29 ms 2124 KB Output is correct
16 Correct 604 ms 26564 KB Output is correct
17 Correct 384 ms 26552 KB Output is correct
18 Correct 383 ms 26656 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 772 KB Output is correct
5 Correct 4 ms 772 KB Output is correct
6 Correct 4 ms 772 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 241 ms 26576 KB Output is correct
9 Correct 194 ms 12700 KB Output is correct
10 Correct 546 ms 26672 KB Output is correct
11 Correct 370 ms 26640 KB Output is correct
12 Correct 365 ms 26600 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 247 ms 26620 KB Output is correct
15 Correct 26 ms 2096 KB Output is correct
16 Correct 598 ms 26852 KB Output is correct
17 Correct 386 ms 26608 KB Output is correct
18 Correct 389 ms 26552 KB Output is correct
19 Correct 517 ms 46852 KB Output is correct
20 Correct 498 ms 44504 KB Output is correct
21 Correct 499 ms 46972 KB Output is correct
22 Correct 494 ms 44456 KB Output is correct
23 Correct 504 ms 44516 KB Output is correct
24 Correct 489 ms 44548 KB Output is correct
25 Correct 502 ms 44440 KB Output is correct
26 Correct 491 ms 47048 KB Output is correct
27 Correct 491 ms 46868 KB Output is correct
28 Correct 498 ms 44456 KB Output is correct
29 Correct 489 ms 44472 KB Output is correct
30 Correct 500 ms 44436 KB Output is correct