oj.uz

Submission #1099509

# Submission time Handle Problem Language Result Execution time Memory
1099509 2024-10-11T13:45:08 Z rahidilbayramli Wall (IOI14_wall) C++17
100 / 100
 979 ms 69504 KB 
#include "wall.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<int, int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll sz = 2e6+5;
ll a[sz];
pll segtree[4*sz];
void build(ll v, ll l, ll r)
{
    if(l == r)
        segtree[v] = {0, 0};
    else
    {
        ll mid = (l + r) / 2;
        build(2*v, l, mid);
        build(2*v+1, mid+1, r);
        segtree[v] = {-1, 0};
    }
}
void push1(ll v, ll l, ll r)
{
    if(l != r)
    {
        if(segtree[v].f >= segtree[2*v].s)
            segtree[2*v] = {segtree[v].f, segtree[v].f};
        else    if(segtree[v].s <= segtree[2*v].f)
            segtree[2*v] = {segtree[v].s, segtree[v].s};
        else
            segtree[2*v] = {max(segtree[v].f, segtree[2*v].f), min(segtree[v].s, segtree[2*v].s)};
        if(segtree[v].f >= segtree[2*v+1].s)
            segtree[2*v+1] = {segtree[v].f, segtree[v].f};
        else    if(segtree[v].s <= segtree[2*v+1].f)
            segtree[2*v+1] = {segtree[v].s, segtree[v].s};
        else
            segtree[2*v+1] = {max(segtree[v].f, segtree[2*v+1].f), min(segtree[v].s, segtree[2*v+1].s)};
        segtree[v] = {INT_MIN, INT_MAX};
    }
}
void update1(ll v, ll l, ll r, ll tl, ll tr, ll val)
{
    push1(v, l, r);
    if(l > r || l > tr || r < tl)
        return;
    if(tl <= l && r <= tr)
    {
        if(l == r){
            segtree[v] = {max(val, segtree[v].f), max(val, segtree[v].f)};
            return;
        }
        segtree[v] = {val, INT_MAX};
        push1(v, l, r);
        return;
    }
    ll mid = (l + r) / 2;
    update1(2*v, l, mid, tl, tr, val);
    update1(2*v+1, mid+1, r, tl, tr, val);
}
void update2(ll v, ll l, ll r, ll tl, ll tr, ll val)
{
    push1(v, l, r);
    if(l > r || l > tr || r < tl)
        return;
    if(tl <= l && r <= tr)
    {
        if(l == r){
            segtree[v] = {min(val, segtree[v].f), min(val, segtree[v].f)};
            return;
        }
        segtree[v] = {INT_MIN, val};
        push1(v, l, r);
        return;
    }
    ll mid = (l + r) / 2;
    update2(2*v, l, mid, tl, tr, val);
    update2(2*v+1, mid+1, r, tl, tr, val);
}
pll findres(ll v, ll l, ll r, ll tl, ll tr)
{
    if(l > r || l > tr || r < tl)
        return {INT_MIN, INT_MAX};
    push1(v, l, r);
    if(tl <= l && r <= tr)
        return segtree[v];
    ll mid = (l + r) / 2;
    pll lans = findres(2*v, l, mid, tl, tr);
    pll rans = findres(2*v+1, mid+1, r, tl, tr);
    return {max(lans.f, rans.f), 0};
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1, 1, n);
    for(int i = 0; i < k; i++)
    {
        if(op[i] == 1)
            update1(1, 1, n, left[i]+1, right[i]+1, height[i]);
        else
            update2(1, 1, n, left[i]+1, right[i]+1, height[i]);
    }
    for(int i = 0; i < n; i++)
        finalHeight[i] = findres(1, 1, n, i+1, i+1).f;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 6 ms 864 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 5 ms 864 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 84 ms 14036 KB Output is correct
3 Correct 130 ms 8020 KB Output is correct
4 Correct 372 ms 20304 KB Output is correct
5 Correct 236 ms 21564 KB Output is correct
6 Correct 224 ms 19760 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 904 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 89 ms 13908 KB Output is correct
9 Correct 131 ms 8020 KB Output is correct
10 Correct 385 ms 20308 KB Output is correct
11 Correct 228 ms 21440 KB Output is correct
12 Correct 221 ms 19792 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 81 ms 13908 KB Output is correct
15 Correct 28 ms 2128 KB Output is correct
16 Correct 458 ms 20692 KB Output is correct
17 Correct 231 ms 19996 KB Output is correct
18 Correct 230 ms 20060 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 900 KB Output is correct
5 Correct 5 ms 904 KB Output is correct
6 Correct 5 ms 912 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 13904 KB Output is correct
9 Correct 131 ms 8084 KB Output is correct
10 Correct 375 ms 20564 KB Output is correct
11 Correct 238 ms 21392 KB Output is correct
12 Correct 231 ms 19796 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 91 ms 13996 KB Output is correct
15 Correct 27 ms 2136 KB Output is correct
16 Correct 490 ms 20668 KB Output is correct
17 Correct 239 ms 20048 KB Output is correct
18 Correct 234 ms 20048 KB Output is correct
19 Correct 957 ms 69460 KB Output is correct
20 Correct 918 ms 67152 KB Output is correct
21 Correct 893 ms 69504 KB Output is correct
22 Correct 939 ms 66976 KB Output is correct
23 Correct 960 ms 67120 KB Output is correct
24 Correct 955 ms 67152 KB Output is correct
25 Correct 979 ms 66896 KB Output is correct
26 Correct 958 ms 69456 KB Output is correct
27 Correct 928 ms 69460 KB Output is correct
28 Correct 952 ms 67228 KB Output is correct
29 Correct 889 ms 67152 KB Output is correct
30 Correct 943 ms 66968 KB Output is correct