oj.uz

Submission #973996

# Submission time Handle Problem Language Result Execution time Memory
973996 2024-05-02T14:30:55 Z Kavelmydex Wall (IOI14_wall) C++17
100 / 100
 945 ms 102572 KB 
#include <bits/stdc++.h>
// #include "wall.h"
using namespace std;
// #define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define endl "\n"
#define sp ' '
#define pb push_back
#define f first
#define s second
#define sz size()
#define all(x) (x).begin(),(x).end()

#define lc ((x<<1))
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)

const int N = 2e6+1, OO = 1e9, mod = 1e9+7, mx = 5e5+1;
const int dx[]{0,0,1,-1}, dy[]{1,-1,0,0};
void tr(int a, int b){cout << a << sp << b << endl;}
void cmx(int &a, int b){a = max(a,b);}
void cmn(int &a, int b){a = min(a,b);}

int n;
pi t[4*N];
int lazy[4*N];

void prop(int x,int l,int r){
    if(lazy[x] == -1) return;
    t[x].f = t[x].s = lazy[x];
    if(l != r){
        lazy[lc] = lazy[x];
        lazy[rc] = lazy[x];
    }
    lazy[x] = -1;
}   
pi fun(pi x,pi y){
    pi ret;
    ret.f = min(x.f,y.f);
    ret.s = max(x.s,y.s);
    return ret;
}
pi calc(int L,int R, int x=1,int l=1,int r=n){
    if(R < l || r < L) return {OO,-OO};
    prop(x,l,r);
    if(L <= l && r <= R) return t[x];
    return fun(calc(L,R,lc,l,mid),calc(L,R,rc,mid+1,r));
} 
void upd_add(int L, int R, int v, int x=1, int l=1, int r=n){
    prop(x,l,r);
    if(r < L || R < l || t[x].f >= v) return;
    if(L <= l && r <= R && t[x].s < v){
        lazy[x] = v;
        prop(x,l,r);    
        return;     
    }
    upd_add(L,R,v,lc,l,mid);
    upd_add(L,R,v,rc,mid+1,r);
    t[x] = fun(t[lc],t[rc]);
}
void upd_remove(int L, int R, int v, int x=1, int l=1, int r=n){
    prop(x,l,r);
    if(r < L || R < l || t[x].s <= v) return;
    if(L <= l && r <= R && t[x].f > v){
        lazy[x] = v;     
        prop(x,l,r);    
        return;     
    }
    upd_remove(L,R,v,lc,l,mid);
    upd_remove(L,R,v,rc,mid+1,r);
    t[x] = fun(t[lc],t[rc]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    memset(lazy,-1,sizeof(lazy));
    For(i,k){
        left[i]++, right[i]++;
        if(op[i] == 1){
            upd_add(left[i],right[i],height[i],1,1,n);
        }else{
            upd_remove(left[i],right[i],height[i],1,1,n);
        }
    }
    rep(i,1,n+1){
        finalHeight[i-1] = calc(i,i,1,1,n).f;
    }
    return;
}

// int32_t main() {
//     ios::sync_with_stdio(0); cin.tie(0); 
//     // freopen("talent.in", "r", stdin);
//     // freopen("talent.out", "w", stdout);   
//     memset(lazy,-1,sizeof(lazy));
//     int k; cin >> n >> k;
//     int tp,l,r,h; 
//     int op[k],left[k],right[k],height[k],finalHeight[n];
//     For(i,k){
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }
//     buildWall(n,k,op,left,right,height,finalHeight);
//     For(i,n) cout << finalHeight[i] << sp;
//     cout << endl;
//     return 0;   
// }
/*
Just some notices : 
I believe you can do it !
You've done things that were harder ... 
Stay calm and focused  =)
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33372 KB Output is correct
2 Correct 6 ms 33560 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 9 ms 33628 KB Output is correct
5 Correct 9 ms 33628 KB Output is correct
6 Correct 10 ms 33652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33372 KB Output is correct
2 Correct 115 ms 47256 KB Output is correct
3 Correct 61 ms 39152 KB Output is correct
4 Correct 153 ms 51792 KB Output is correct
5 Correct 160 ms 52816 KB Output is correct
6 Correct 179 ms 51112 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33372 KB Output is correct
2 Correct 6 ms 33564 KB Output is correct
3 Correct 5 ms 33500 KB Output is correct
4 Correct 10 ms 33628 KB Output is correct
5 Correct 9 ms 33628 KB Output is correct
6 Correct 9 ms 33628 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 113 ms 47028 KB Output is correct
9 Correct 61 ms 40476 KB Output is correct
10 Correct 159 ms 51584 KB Output is correct
11 Correct 158 ms 52820 KB Output is correct
12 Correct 173 ms 51132 KB Output is correct
13 Correct 5 ms 33368 KB Output is correct
14 Correct 118 ms 46952 KB Output is correct
15 Correct 26 ms 34640 KB Output is correct
16 Correct 365 ms 52048 KB Output is correct
17 Correct 243 ms 53052 KB Output is correct
18 Correct 247 ms 51536 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33372 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33480 KB Output is correct
4 Correct 10 ms 33628 KB Output is correct
5 Correct 11 ms 33648 KB Output is correct
6 Correct 9 ms 33628 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 119 ms 46932 KB Output is correct
9 Correct 62 ms 40528 KB Output is correct
10 Correct 155 ms 51792 KB Output is correct
11 Correct 160 ms 52824 KB Output is correct
12 Correct 183 ms 51172 KB Output is correct
13 Correct 5 ms 33372 KB Output is correct
14 Correct 119 ms 47012 KB Output is correct
15 Correct 27 ms 34396 KB Output is correct
16 Correct 363 ms 52152 KB Output is correct
17 Correct 245 ms 53076 KB Output is correct
18 Correct 253 ms 51280 KB Output is correct
19 Correct 892 ms 101200 KB Output is correct
20 Correct 945 ms 98504 KB Output is correct
21 Correct 887 ms 102480 KB Output is correct
22 Correct 878 ms 100032 KB Output is correct
23 Correct 898 ms 100020 KB Output is correct
24 Correct 891 ms 99984 KB Output is correct
25 Correct 883 ms 98640 KB Output is correct
26 Correct 900 ms 102572 KB Output is correct
27 Correct 893 ms 102452 KB Output is correct
28 Correct 905 ms 99936 KB Output is correct
29 Correct 920 ms 98312 KB Output is correct
30 Correct 895 ms 98336 KB Output is correct