oj.uz

Submission #973999

# Submission time Handle Problem Language Result Execution time Memory
973999 2024-05-02T14:44:47 Z Kavelmydex Wall (IOI14_wall) C++17
100 / 100
 1181 ms 120532 KB 
#include <bits/stdc++.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;
struct node {
    int mx,mn,lazy=-1;
};
node t[4*N];
 
void prop(int x,int l,int r){
    if(t[x].lazy == -1) return;
    t[x].mn = t[x].mx = t[x].lazy;
    if(l != r){
        t[lc].lazy = t[x].lazy;
        t[rc].lazy = t[x].lazy;
    }
    t[x].lazy = -1;
}   
node fun(node x,node y){
    node ret;
    ret.mn = min(x.mn,y.mn);
    ret.mx = max(x.mx,y.mx);
    return ret;
}
node calc(int L,int R, int x=1,int l=1,int r=n){
    if(R < l || r < L) return {-OO,OO,-1};
    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].mn >= v) return;
    if(L <= l && r <= R && t[x].mx < v){
        t[x].lazy = 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].mx <= v) return;
    if(L <= l && r <= R && t[x].mn > v){
        t[x].lazy = 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[]){
    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).mn;
    }
    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 60 ms 94172 KB Output is correct
2 Correct 15 ms 94300 KB Output is correct
3 Correct 15 ms 94300 KB Output is correct
4 Correct 20 ms 94452 KB Output is correct
5 Correct 19 ms 94484 KB Output is correct
6 Correct 18 ms 94296 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 94304 KB Output is correct
2 Correct 114 ms 102136 KB Output is correct
3 Correct 68 ms 97616 KB Output is correct
4 Correct 164 ms 102792 KB Output is correct
5 Correct 169 ms 103364 KB Output is correct
6 Correct 186 ms 103492 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 94296 KB Output is correct
2 Correct 14 ms 94300 KB Output is correct
3 Correct 14 ms 94296 KB Output is correct
4 Correct 22 ms 94296 KB Output is correct
5 Correct 18 ms 94300 KB Output is correct
6 Correct 19 ms 94496 KB Output is correct
7 Correct 14 ms 94300 KB Output is correct
8 Correct 110 ms 101968 KB Output is correct
9 Correct 69 ms 97692 KB Output is correct
10 Correct 185 ms 102592 KB Output is correct
11 Correct 212 ms 103248 KB Output is correct
12 Correct 185 ms 103252 KB Output is correct
13 Correct 16 ms 94452 KB Output is correct
14 Correct 131 ms 101984 KB Output is correct
15 Correct 37 ms 94812 KB Output is correct
16 Correct 389 ms 102916 KB Output is correct
17 Correct 272 ms 102992 KB Output is correct
18 Correct 261 ms 102964 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 94296 KB Output is correct
2 Correct 15 ms 94296 KB Output is correct
3 Correct 16 ms 94192 KB Output is correct
4 Correct 23 ms 94472 KB Output is correct
5 Correct 19 ms 94300 KB Output is correct
6 Correct 18 ms 94300 KB Output is correct
7 Correct 14 ms 94300 KB Output is correct
8 Correct 111 ms 101972 KB Output is correct
9 Correct 82 ms 97704 KB Output is correct
10 Correct 166 ms 102712 KB Output is correct
11 Correct 178 ms 103272 KB Output is correct
12 Correct 187 ms 103236 KB Output is correct
13 Correct 13 ms 94252 KB Output is correct
14 Correct 116 ms 101964 KB Output is correct
15 Correct 37 ms 94988 KB Output is correct
16 Correct 390 ms 102804 KB Output is correct
17 Correct 284 ms 103172 KB Output is correct
18 Correct 262 ms 102948 KB Output is correct
19 Correct 1091 ms 120120 KB Output is correct
20 Correct 1100 ms 117928 KB Output is correct
21 Correct 1125 ms 120308 KB Output is correct
22 Correct 1080 ms 117780 KB Output is correct
23 Correct 1077 ms 117936 KB Output is correct
24 Correct 1181 ms 117580 KB Output is correct
25 Correct 1096 ms 117916 KB Output is correct
26 Correct 1149 ms 120532 KB Output is correct
27 Correct 1097 ms 120224 KB Output is correct
28 Correct 1122 ms 117728 KB Output is correct
29 Correct 1086 ms 117696 KB Output is correct
30 Correct 1140 ms 117604 KB Output is correct