oj.uz

Submission #597025

# Submission time Handle Problem Language Result Execution time Memory
597025 2022-07-15T11:58:13 Z Bench0310 Wall (IOI14_wall) C++17
100 / 100
 701 ms 169920 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
typedef long long ll;

const int inf=(1<<30);

struct node
{
    int a,b;
    node(){a=0;b=inf;}
    node(int x,int y){a=x;b=y;}
    int eval(int x)
    {
        if(x<=a) return a;
        else if(a<=x&&x<=b) return x;
        else return b;
    }
    void pull(node &l,node &r)
    {
        a=r.eval(l.a);
        b=r.eval(l.b);
    }
};

const int N=500000;
node tree[4*N];

void update(int idx,int l,int r,int pos,node x)
{
    if(l==r) tree[idx]=x;
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx].pull(tree[2*idx],tree[2*idx+1]);
    }
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int res[])
{
    vector<int> add[n];
    vector<int> rm[n];
    for(int i=0;i<k;i++)
    {
        add[left[i]].push_back(i);
        rm[right[i]].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        for(int j:add[i])
        {
            if(op[j]==1) update(1,0,k-1,j,node(height[j],inf));
            else update(1,0,k-1,j,node(0,height[j]));
        }
        res[i]=tree[1].a;
        for(int j:rm[i]) update(1,0,k-1,j,node());
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 10 ms 16084 KB Output is correct
3 Correct 9 ms 15956 KB Output is correct
4 Correct 12 ms 16864 KB Output is correct
5 Correct 12 ms 16796 KB Output is correct
6 Correct 12 ms 16736 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15920 KB Output is correct
2 Correct 300 ms 33812 KB Output is correct
3 Correct 198 ms 27228 KB Output is correct
4 Correct 596 ms 48156 KB Output is correct
5 Correct 313 ms 46288 KB Output is correct
6 Correct 340 ms 44468 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 12 ms 16088 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Correct 12 ms 16852 KB Output is correct
5 Correct 12 ms 16816 KB Output is correct
6 Correct 12 ms 16852 KB Output is correct
7 Correct 8 ms 15952 KB Output is correct
8 Correct 263 ms 33844 KB Output is correct
9 Correct 214 ms 27216 KB Output is correct
10 Correct 620 ms 48040 KB Output is correct
11 Correct 313 ms 46300 KB Output is correct
12 Correct 299 ms 44424 KB Output is correct
13 Correct 8 ms 15956 KB Output is correct
14 Correct 267 ms 33688 KB Output is correct
15 Correct 35 ms 18652 KB Output is correct
16 Correct 701 ms 48376 KB Output is correct
17 Correct 337 ms 44808 KB Output is correct
18 Correct 323 ms 45020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 13 ms 16088 KB Output is correct
3 Correct 9 ms 15956 KB Output is correct
4 Correct 14 ms 16872 KB Output is correct
5 Correct 12 ms 16824 KB Output is correct
6 Correct 12 ms 16732 KB Output is correct
7 Correct 10 ms 15896 KB Output is correct
8 Correct 260 ms 33612 KB Output is correct
9 Correct 210 ms 27204 KB Output is correct
10 Correct 575 ms 48260 KB Output is correct
11 Correct 356 ms 46304 KB Output is correct
12 Correct 312 ms 44360 KB Output is correct
13 Correct 8 ms 15952 KB Output is correct
14 Correct 270 ms 33624 KB Output is correct
15 Correct 35 ms 18764 KB Output is correct
16 Correct 642 ms 48304 KB Output is correct
17 Correct 342 ms 44976 KB Output is correct
18 Correct 319 ms 44964 KB Output is correct
19 Correct 595 ms 169920 KB Output is correct
20 Correct 566 ms 167328 KB Output is correct
21 Correct 560 ms 169820 KB Output is correct
22 Correct 555 ms 167208 KB Output is correct
23 Correct 570 ms 167196 KB Output is correct
24 Correct 581 ms 167244 KB Output is correct
25 Correct 542 ms 167144 KB Output is correct
26 Correct 582 ms 169684 KB Output is correct
27 Correct 574 ms 169800 KB Output is correct
28 Correct 567 ms 167196 KB Output is correct
29 Correct 638 ms 167168 KB Output is correct
30 Correct 605 ms 167196 KB Output is correct