oj.uz

Submission #1016677

# Submission time Handle Problem Language Result Execution time Memory
1016677 2024-07-08T10:18:19 Z serkanrashid Wall (IOI14_wall) C++14
32 / 100
 431 ms 26448 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int ch,ty;
    Node()
    {
        ch = -1;
        ty = 0;
    };
    Node(int chi, int ti)
    {
        ch = chi;
        ty = ti;
    }
};

const int maxn = 2e5+5;

int type,ql,qr,val;
Node lazy[4*maxn];
int tree[maxn];

void push_lazy(int v, int l, int r)
{
    if(lazy[v].ty==0) return;

    ///cout << v << " " << l << " " << r << endl;
    ///cout << lazy[v].ch << " " << lazy[v].ty << endl;
    if(l!=r)
    {
        lazy[v*2+0].ty = lazy[v*2+1].ty = lazy[v].ty;
        if(lazy[v].ty==1)
        {
            lazy[v*2+0].ch = max(lazy[v*2+0].ch,lazy[v].ch);
            lazy[v*2+1].ch = max(lazy[v*2+1].ch,lazy[v].ch);
        }
        else
        {
            if(lazy[v*2+0].ch==-1) lazy[v*2+0].ch = lazy[v].ch;
            else lazy[v*2+0].ch = min(lazy[v*2+0].ch,lazy[v].ch);
            if(lazy[v*2+1].ch==-1) lazy[v*2+1].ch = lazy[v].ch;
            else lazy[v*2+1].ch = min(lazy[v*2+1].ch,lazy[v].ch);
        }
    }
    else
    {
        if(lazy[v].ty==1) tree[r] = max(tree[r],lazy[v].ch);
        else tree[r] = min(tree[r],lazy[v].ch);
    }

    lazy[v].ch = -1;
    lazy[v].ty = 0;
}

void query(int v, int l, int r)
{
    ///cout << "query" << endl;
    push_lazy(v,l,r);
    if(l==r) return;
    int mid = (l+r)/2;
    query(v*2+0,l,mid+0);
    query(v*2+1,mid+1,r);
}

void update(int v, int l, int r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return;
    if(ql<=l&&r<=qr)
    {
        lazy[v] = {val,type};
        push_lazy(v,l,r);
        ///
        return;
    }
    int mid = (l+r)/2;
    update(v*2+0,l,mid+0);
    update(v*2+1,mid+1,r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    if(n<=10000)
    {
        for(int i = 0; i < k; i++)
    {
        type = op[i];
        ql = left[i];
        qr = right[i];
        val = height[i];
        for(int j = ql; j <= qr; j++)
        {
            if(type==1) tree[j] = max(tree[j],val);
            else tree[j] = min(tree[j],val);
        }
    }
    for(int i = 0; i < n; i++) finalHeight[i] = tree[i];
        return;
    }
    bool f = true;
    for(int i = 0; i < k; i++)
    {
        if(f&&op[i]==2)
        {
            query(1,0,n-1);
            f = false;
        }
        type = op[i];
        ql = left[i];
        qr = right[i];
        val = height[i];
        update(1,0,n-1);
    }
    query(1,0,n-1);
    for(int i = 0; i < n; i++) finalHeight[i] = tree[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 21 ms 7516 KB Output is correct
5 Correct 13 ms 7548 KB Output is correct
6 Correct 13 ms 7516 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 118 ms 15124 KB Output is correct
3 Correct 132 ms 10580 KB Output is correct
4 Correct 410 ms 15692 KB Output is correct
5 Correct 175 ms 16212 KB Output is correct
6 Correct 169 ms 16328 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 12 ms 7544 KB Output is correct
5 Correct 13 ms 7516 KB Output is correct
6 Correct 12 ms 7548 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 81 ms 19528 KB Output is correct
9 Correct 124 ms 13652 KB Output is correct
10 Correct 403 ms 23012 KB Output is correct
11 Correct 200 ms 26356 KB Output is correct
12 Correct 178 ms 24800 KB Output is correct
13 Correct 1 ms 7260 KB Output is correct
14 Correct 83 ms 20732 KB Output is correct
15 Incorrect 24 ms 8532 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 13 ms 7548 KB Output is correct
5 Correct 13 ms 7516 KB Output is correct
6 Correct 13 ms 7516 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 87 ms 19432 KB Output is correct
9 Correct 119 ms 13652 KB Output is correct
10 Correct 431 ms 23116 KB Output is correct
11 Correct 176 ms 26448 KB Output is correct
12 Correct 177 ms 24916 KB Output is correct
13 Correct 1 ms 7256 KB Output is correct
14 Correct 108 ms 20900 KB Output is correct
15 Incorrect 23 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -