oj.uz

Submission #737207

# Submission time Handle Problem Language Result Execution time Memory
737207 2023-05-06T20:43:38 Z Boomyday Wall (IOI14_wall) C++17
100 / 100
 918 ms 92180 KB 


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//
// Created by adavy on 3/14/2023.
//
//
// Created by adavy on 1/31/2023.
//
// My Header
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second



#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!







struct nd{
    ll mn=0,  mx=INF;
    nd(){};
    nd(ll mn, ll mx){
        this->mn = mn; this->mx = mx;
    }
    void operator+=(const nd& other){
        this->mn = min(max(this->mn, other.mn),other.mx);
        this->mx = min(max(this->mx, other.mn),other.mx);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    ll segsize = floor(1<<(int)(log2(n)+1));
    //cout << segsize << endl;
    vector<nd> seg(2*segsize);

    function<void(int, int, int)> pushdown = [&](int rt, int tl, int tr){
        if (tl != tr){
            seg[2*rt] += seg[rt]; seg[2*rt+1] += seg[rt]; seg[rt] = nd();
        }
    };

    function<void(nd, int, int, int, int, int)> update
    = [&](nd Nd, int l, int r, int rt, int tl, int tr){
        if (r < tl || l > tr) return;
        if (l==tl && tr==r){seg[rt] += Nd; return;}
        pushdown(rt, tl, tr);
        int tm = (tl+tr)/2;
        update(Nd, l, min(r, tm), 2*rt, tl, tm);
        update(Nd, max(l, tm+1), r, 2*rt+1, tm+1, tr);
    };

    F0R(i, k){
        if (op[i]==1) {
            update(nd(height[i],INF),left[i],right[i],1,0,segsize-1);
        }
        else {
            update(nd(0,height[i]),left[i],right[i],1,0,segsize-1);
        }
    }


    F0R(i, segsize) pushdown(i, 0, segsize-1);
    FOR(i, segsize, segsize+n) finalHeight[i-segsize] = seg[i].mn;

}

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

 */

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 932 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 9 ms 980 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 153 ms 13900 KB Output is correct
3 Correct 270 ms 8416 KB Output is correct
4 Correct 670 ms 22280 KB Output is correct
5 Correct 420 ms 22776 KB Output is correct
6 Correct 423 ms 21136 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 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 7 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 163 ms 13892 KB Output is correct
9 Correct 267 ms 8416 KB Output is correct
10 Correct 726 ms 22232 KB Output is correct
11 Correct 397 ms 22880 KB Output is correct
12 Correct 386 ms 21216 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 150 ms 13900 KB Output is correct
15 Correct 39 ms 2396 KB Output is correct
16 Correct 687 ms 22228 KB Output is correct
17 Correct 382 ms 21568 KB Output is correct
18 Correct 392 ms 21648 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 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 6 ms 952 KB Output is correct
6 Correct 6 ms 1008 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 148 ms 13828 KB Output is correct
9 Correct 241 ms 8384 KB Output is correct
10 Correct 648 ms 22276 KB Output is correct
11 Correct 398 ms 22832 KB Output is correct
12 Correct 388 ms 21192 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 151 ms 13936 KB Output is correct
15 Correct 39 ms 2328 KB Output is correct
16 Correct 702 ms 22228 KB Output is correct
17 Correct 391 ms 21764 KB Output is correct
18 Correct 409 ms 21744 KB Output is correct
19 Correct 908 ms 92116 KB Output is correct
20 Correct 911 ms 92036 KB Output is correct
21 Correct 918 ms 92180 KB Output is correct
22 Correct 900 ms 92128 KB Output is correct
23 Correct 884 ms 92180 KB Output is correct
24 Correct 903 ms 92068 KB Output is correct
25 Correct 894 ms 92124 KB Output is correct
26 Correct 901 ms 92072 KB Output is correct
27 Correct 897 ms 91988 KB Output is correct
28 Correct 888 ms 91968 KB Output is correct
29 Correct 906 ms 92104 KB Output is correct
30 Correct 909 ms 92036 KB Output is correct