oj.uz

Submission #1026890

# Submission time Handle Problem Language Result Execution time Memory
1026890 2024-07-18T13:04:44 Z khanhtb Wall (IOI14_wall) C++14
100 / 100
 521 ms 237908 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 2e6 + 8;
ll ans[N];
struct Segment_Tree{
    vpll st;
    vi lz;
    void init(ll n){
        st = vpll(n<<2);
        lz = vi(n<<2,-1);
    }
    void update_node(ll id, ll x){
        st[id].fi = st[id].se = x;
        lz[id] = x;
    }
    void push(ll id){
        if(lz[id] == -1) return;
        update_node(id<<1,lz[id]);
        update_node(id<<1|1,lz[id]);
        lz[id] = -1;
    }
    void update(ll id, ll l, ll r, ll u, ll v, ll x, bool type){
        if(v < l || r < u) return;
        if(!type && st[id].fi >= x) return;
        if(type && st[id].se <= x) return;
        if(u <= l && r <= v){
            if(!type && st[id].se <= x){
                update_node(id,x);
                return;
            }
            if(type && st[id].fi >= x){
                update_node(id,x);
                return;
            }
        }
        push(id);
        ll m = l+r>>1;
        update(id<<1,l,m,u,v,x,type);
        update(id<<1|1,m+1,r,u,v,x,type);
        st[id].fi = min(st[id<<1].fi,st[id<<1|1].fi);
        st[id].se = max(st[id<<1].se, st[id<<1|1].se);
    }
    void get(ll id, ll l, ll r){
        if(l == r){
            ans[l] = st[id].se;
            return;
        }
        push(id);
        ll m = l+r>>1;
        get(id<<1,l,m);
        get(id<<1|1,m+1,r);
    }
} st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.init(n);
    for(ll i = 0; i < k; i++){
        left[i]++,right[i]++;
        if(op[i] == 1) st.update(1,1,n,left[i],right[i],height[i],0);
        if(op[i] == 2) st.update(1,1,n,left[i],right[i],height[i],1);
    }
    st.get(1,1,n);
    for(ll i = 0; i < n; i++) finalHeight[i] = ans[i+1];
}

Compilation message

wall.cpp: In member function 'void Segment_Tree::update(long long int, long long int, long long int, long long int, long long int, long long int, bool)':
wall.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         ll m = l+r>>1;
      |                ~^~
wall.cpp: In member function 'void Segment_Tree::get(long long int, long long int, long long int)':
wall.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         ll m = l+r>>1;
      |                ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1600 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 3 ms 1664 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 123 ms 12788 KB Output is correct
3 Correct 49 ms 8652 KB Output is correct
4 Correct 119 ms 27984 KB Output is correct
5 Correct 134 ms 28764 KB Output is correct
6 Correct 138 ms 27984 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1692 KB Output is correct
5 Correct 4 ms 1624 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 12912 KB Output is correct
9 Correct 94 ms 8668 KB Output is correct
10 Correct 126 ms 27988 KB Output is correct
11 Correct 125 ms 28748 KB Output is correct
12 Correct 156 ms 27804 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 104 ms 12728 KB Output is correct
15 Correct 25 ms 3380 KB Output is correct
16 Correct 341 ms 28244 KB Output is correct
17 Correct 207 ms 27732 KB Output is correct
18 Correct 223 ms 27676 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1600 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 129 ms 12676 KB Output is correct
9 Correct 51 ms 8508 KB Output is correct
10 Correct 129 ms 27976 KB Output is correct
11 Correct 133 ms 28868 KB Output is correct
12 Correct 150 ms 27644 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 103 ms 12832 KB Output is correct
15 Correct 18 ms 3164 KB Output is correct
16 Correct 345 ms 28424 KB Output is correct
17 Correct 208 ms 27656 KB Output is correct
18 Correct 200 ms 27728 KB Output is correct
19 Correct 487 ms 237880 KB Output is correct
20 Correct 474 ms 235532 KB Output is correct
21 Correct 494 ms 237908 KB Output is correct
22 Correct 458 ms 235392 KB Output is correct
23 Correct 446 ms 235428 KB Output is correct
24 Correct 443 ms 235480 KB Output is correct
25 Correct 446 ms 235600 KB Output is correct
26 Correct 512 ms 237904 KB Output is correct
27 Correct 462 ms 237904 KB Output is correct
28 Correct 521 ms 235540 KB Output is correct
29 Correct 480 ms 235576 KB Output is correct
30 Correct 474 ms 235512 KB Output is correct