oj.uz

Submission #544519

# Submission time Handle Problem Language Result Execution time Memory
544519 2022-04-02T07:40:56 Z SavicS Wall (IOI14_wall) C++17
100 / 100
 813 ms 86092 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 2000005; 

int n, q;

// min, max

int mx[4 * mxN];
int mn[4 * mxN];
int lenj[4 * mxN];

void build(int v, int tl, int tr){
    lenj[v] = -1; mx[v] = mn[v] = 0;
    if(tl == tr)return;
    int mid = (tl + tr) / 2;
    build(v * 2, tl, mid); 
    build(v * 2 + 1, mid + 1, tr);
}

void propagate(int v, int tl, int tr){
    if(lenj[v] != -1){
        mn[v] = mx[v] = lenj[v];
        if(tl != tr){
            lenj[v * 2] = lenj[v];
            lenj[v * 2 + 1] = lenj[v];
        }
        lenj[v] = -1;
    }   
}

// add
void lazyupd_add(int v, int tl, int tr, int l, int r, int val){
    propagate(v, tl, tr);
    if(tl > tr || l > tr || tl > r)return;
    if(tl >= l && tr <= r){

        if(mx[v] <= val){
            lenj[v] = val;
            propagate(v, tl, tr);
            return;
        }

        if(mn[v] >= val){
            return;
        }

    }

    int mid = (tl + tr) / 2;
    lazyupd_add(v * 2, tl, mid, l, r, val); lazyupd_add(v * 2 + 1, mid + 1, tr, l, r, val);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}

// rem
void lazyupd_rem(int v, int tl, int tr, int l, int r, int val){
    propagate(v, tl, tr);
    if(tl > tr || l > tr || tl > r)return;
    if(tl >= l && tr <= r){

        if(mn[v] >= val){
            lenj[v] = val;
            propagate(v, tl, tr);
            return;
        }

        if(mx[v] <= val){
            return;
        }

    }

    int mid = (tl + tr) / 2;
    lazyupd_rem(v * 2, tl, mid, l, r, val); lazyupd_rem(v * 2 + 1, mid + 1, tr, l, r, val);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}

int get(int v, int tl, int tr, int pos){
    propagate(v, tl, tr);
    if(tl == tr)return mn[v];
    int mid = (tl + tr) / 2;
    if(pos <= mid)return get(v * 2, tl, mid, pos);
    else return get(v * 2 + 1, mid + 1, tr, pos);
}

void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = _n; q = _k; 



    ff(i,0,q){
        int t = op[i];
        int l = left[i];
        int r = right[i];
        int h = height[i];

        if(t == 1){
            // add
            lazyupd_add(1,0,n - 1,l,r,h);
        }

        if(t == 2){
            // remove
            lazyupd_rem(1,0,n - 1,l,r,h);
        }

    }

    ff(i,0,n - 1)finalHeight[i] = get(1,0,n - 1,i);

}

// int main() {
//     cin.tie(0)->sync_with_stdio(0);

//     int _n, _q;
//     cin >> _n >> _q;

//     int O[_q], L[_q], R[_q], H[_q];
//     ff(i,0,_q - 1){
//         cin >> O[i] >> L[i] >> R[i] >> H[i];
//     }

//     int res[_n];
//     buildWall(_n, _q, O, L, R, H, res);

//     return 0;
// }
/*
 
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

 
// probati bojenje sahovski
*/

Subtask #1
8.0 / 8.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 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 131 ms 8096 KB Output is correct
3 Correct 160 ms 4408 KB Output is correct
4 Correct 461 ms 11744 KB Output is correct
5 Correct 307 ms 12236 KB Output is correct
6 Correct 291 ms 12268 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 412 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 151 ms 8188 KB Output is correct
9 Correct 159 ms 4428 KB Output is correct
10 Correct 426 ms 11820 KB Output is correct
11 Correct 297 ms 12328 KB Output is correct
12 Correct 302 ms 12260 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 138 ms 8136 KB Output is correct
15 Correct 33 ms 1724 KB Output is correct
16 Correct 595 ms 12004 KB Output is correct
17 Correct 357 ms 12180 KB Output is correct
18 Correct 285 ms 11980 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 2 ms 340 KB Output is correct
4 Correct 7 ms 812 KB Output is correct
5 Correct 5 ms 836 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 8052 KB Output is correct
9 Correct 159 ms 4404 KB Output is correct
10 Correct 446 ms 11792 KB Output is correct
11 Correct 293 ms 12236 KB Output is correct
12 Correct 298 ms 12208 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 140 ms 8044 KB Output is correct
15 Correct 36 ms 1612 KB Output is correct
16 Correct 562 ms 12136 KB Output is correct
17 Correct 300 ms 12028 KB Output is correct
18 Correct 284 ms 12008 KB Output is correct
19 Correct 805 ms 75632 KB Output is correct
20 Correct 798 ms 83496 KB Output is correct
21 Correct 809 ms 85980 KB Output is correct
22 Correct 791 ms 83396 KB Output is correct
23 Correct 813 ms 83408 KB Output is correct
24 Correct 795 ms 83472 KB Output is correct
25 Correct 770 ms 83404 KB Output is correct
26 Correct 796 ms 86092 KB Output is correct
27 Correct 797 ms 85944 KB Output is correct
28 Correct 791 ms 83480 KB Output is correct
29 Correct 788 ms 83372 KB Output is correct
30 Correct 778 ms 83396 KB Output is correct