oj.uz

Submission #863999

# Submission time Handle Problem Language Result Execution time Memory
863999 2023-10-21T16:33:50 Z thegamercoder19 Wall (IOI14_wall) C++14
61 / 100
 519 ms 262144 KB 
#include "wall.h"
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846
#define FILER 0
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = pow(10, 9) + 7;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const ull INFUL = 0x3f3f3f3f3f3f3f3f;
const ll INFT = 0x3f3f3f3f;
const ull MAX = 1LL << 24;
const ll MODD = 998244353;
const double EPS = 1e-10;
#define V vector
#define pll pair<ll, ll>
#define pull2 pair<ull,ull>
#define MS multiset
#define M map
#define Q queue
#define PQ priority_queue
#define IOF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
#define FORR(typ,i,a,b,c) for(typ i = a; i > b; i -= c)
#define FORA(a,i) for(auto &i : a)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define sorta(a) sort(all(a))
#define sortd(a) sort(all(a), greater<ll>())
#define setp(x) setprecision(x)<<fixed
#define RET return
#define log(a,b) log(b)/log(a)
#define WH(s) while(s)
#define WHI(t) WH(t--)
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define YESNO(s) cout << (s ? "YES" : "NO") << endl;
#define YesNo(s) cout<<(s?"Yes":"No")<<endl;
#define TYP 0
using namespace std;


struct node
{
    ll mx, smx, cmx, mn, smn, cmn;
};

V<node> st;
ll n, q, c, l, r, h;
void merge(ll u)
{

    if (st[u << 1].mx == st[u << 1 | 1].mx)
    {
        st[u].cmx = st[u << 1].cmx + st[u << 1 | 1].cmx;
        st[u].mx = st[u << 1].mx;
        st[u].smx = max(st[u << 1].smx, st[u << 1 | 1].smx);
    }
    else
    {
        st[u].mx = max(st[u << 1].mx, st[u << 1 | 1].mx);
        if (st[u << 1].mx > st[u << 1 | 1].mx)
        {
            st[u].smx = max(st[u << 1].smx, st[u << 1 | 1].mx);
            st[u].cmx = st[u << 1].cmx;
        }
        else
        {
            st[u].smx = max(st[u << 1 | 1].smx, st[u << 1].mx);
            st[u].cmx = st[u << 1 | 1].cmx;
        }
    }

    if (st[u << 1].mn == st[u << 1 | 1].mn)
    {
        st[u].cmn = st[u << 1].cmn + st[u << 1 | 1].cmn;
        st[u].mn = st[u << 1].mn;
        st[u].smn = min(st[u << 1].smn, st[u << 1 | 1].smn);
    }
    else
    {
        st[u].mn = min(st[u << 1].mn, st[u << 1 | 1].mn);
        if (st[u << 1].mn < st[u << 1 | 1].mn)
        {
            st[u].smn = min(st[u << 1].smn, st[u << 1 | 1].mn);
            st[u].cmn = st[u << 1].cmn;
        }
        else
        {
            st[u].smn = min(st[u << 1 | 1].smn, st[u << 1].mn);
            st[u].cmn = st[u << 1 | 1].cmn;
        }
    }
}

void push_min(ll u, ll h, ll l, ll r)
{
    if (h <= st[u].mn)RET;
    st[u].mn = h;
    if (l == r)st[u].mx = st[u].mn;
    else
    {
        if (st[u].mx <= h)st[u].mx = h;
        else if (st[u].smx < h)st[u].smx = h;
    }
}


void push_max(ll u, ll h, ll l, ll r)
{
    if (h >= st[u].mx)RET;
    st[u].mx = h;
    if (l == r)st[u].mn = st[u].mx;
    else
    {
        if (st[u].mn >= h)st[u].mn = h;
        else if (st[u].smn > h)st[u].smn = h;
    }
}

void push_down(ll u, ll l, ll r)
{
    ll m = (l + r) >> 1;
    push_max(u << 1, st[u].mx, l, m); push_max(u << 1 | 1, st[u].mx, m + 1, r);
    push_min(u << 1, st[u].mn, l, m); push_min(u << 1 | 1, st[u].mn, m + 1, r);
}


void add(ll u, ll l, ll r, ll ql, ll qr, ll h)
{
    if (l > r || qr < l || ql > r || st[u].mn >= h) RET;
    if (ql <= l && r <= qr && st[u].smn > h)
    {
        push_min(u, h, l, r);
        RET;
    }
    push_down(u, l, r);
    ll m = (l + r) >> 1;
    add(u << 1, l, m, ql, qr, h); add(u << 1 | 1, m + 1, r, ql, qr, h);
    merge(u);
}

void sub(ll u, ll l, ll r, ll ql, ll qr, ll h)
{
    if (l > r || qr < l || ql > r || st[u].mx <= h) RET;
    if (ql <= l && r <= qr && st[u].smx < h)
    {
        push_max(u, h, l, r);
        RET;
    }
    push_down(u, l, r);
    ll m = (l + r) >> 1;
    sub(u << 1, l, m, ql, qr, h); sub(u << 1 | 1, m + 1, r, ql, qr, h);
    merge(u);
}

ll get(ll u, ll l, ll r, ll p)
{
    if (l > r)RET 0;

    if (l == r)
        RET st[u].mn;
    push_down(u, l, r);
    ll m = (l + r) >> 1;
    if (p <= m)RET get(u << 1, l, m, p);
    RET get(u << 1 | 1, m + 1, r, p);
}

void build(ll u, ll l, ll r)
{
    if (l == r) { st[u].mx = st[u].mn = 0; st[u].smx = -INFL, st[u].smn = INFL; st[u].cmn = st[u].cmx = 1; RET; }
    ll m = (l + r) >> 1;
    build(u << 1, l, m); build(u << 1 | 1, m + 1, r);
    merge(u);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.resize(4 * n + 4);
    build(1, 0, n - 1);
    FOR(ll, i, 0, k, 1)
    {
        if (op[i]==1) add(1, 0, n-1, left[i], right[i], height[i]);
        else sub(1, 0, n - 1, left[i], right[i], height[i]);
    }
    FOR(ll, i, 0, n, 1)finalHeight[i] = get(1, 0, n - 1, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 2648 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 104 ms 13908 KB Output is correct
3 Correct 58 ms 10784 KB Output is correct
4 Correct 153 ms 37200 KB Output is correct
5 Correct 153 ms 38224 KB Output is correct
6 Correct 182 ms 36688 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 8 ms 2396 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2408 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 101 ms 13984 KB Output is correct
9 Correct 58 ms 10836 KB Output is correct
10 Correct 155 ms 37196 KB Output is correct
11 Correct 153 ms 38228 KB Output is correct
12 Correct 210 ms 36688 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 111 ms 14200 KB Output is correct
15 Correct 30 ms 4696 KB Output is correct
16 Correct 519 ms 37500 KB Output is correct
17 Correct 283 ms 36816 KB Output is correct
18 Correct 274 ms 36728 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 7 ms 2424 KB Output is correct
5 Correct 6 ms 2580 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 101 ms 13908 KB Output is correct
9 Correct 57 ms 10960 KB Output is correct
10 Correct 151 ms 37716 KB Output is correct
11 Correct 152 ms 38228 KB Output is correct
12 Correct 178 ms 36688 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 105 ms 13884 KB Output is correct
15 Correct 34 ms 4708 KB Output is correct
16 Correct 514 ms 37456 KB Output is correct
17 Correct 295 ms 36852 KB Output is correct
18 Correct 274 ms 37116 KB Output is correct
19 Runtime error 210 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -