oj.uz

Submission #930535

# Submission time Handle Problem Language Result Execution time Memory
930535 2024-02-20T05:52:59 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 713 ms 143716 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 12, MOD = 998244353;

typedef long long ll;

#include "wall.h"

int mx[N * 4],mn[N * 4],_n,_mn[N * 4],_mx[N * 4],res[N];
void pull(int v,int val,bool ok){
    if(!ok){
        if(val >= mx[v]){
            mn[v] = _mn[v] = _mx[v] = mx[v] = val;
        }else if(val >= mn[v]){
            mn[v] = _mn[v] = val;
        }
    }else{
        if(val <= mn[v]){
            mn[v] = _mn[v] = _mx[v] = mx[v] = val;
        }else if(val <= mx[v]){
            mx[v] = _mx[v] = val;
        }
    }
//    cout << ok << ' ' << v << ' ' << _mn[v] << ' ' << _mx[v] << '\n';
}
void push(int v){
    if(_mn[v] != -1){
        mn[v + v] = _mn[v +v + 1] = mn[v + v + 1] = _mn[v + v] = _mn[v];
        _mn[v] = -1;
    }
    if(_mx[v] != -1){
        mx[v + v] = _mx[v +v + 1] = mx[v + v + 1] = _mx[v + v] = _mx[v];
        _mx[v] = -1;
    }
}
void upd(int l,int r,int val,bool ok,int v = 1,int tl = 1,int tr = _n){
//    cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << val << ' ' << ok << '\n';
    if(l > r || tl > r || l > tr) return;
//    cout << ok << "x\n";
    if(tl >= l && tr <= r && mx[v] - mn[v] <= 1){
//        cout << mn[v] << ' ' << mx[v] << '\n';
        pull(v,val,ok);
//        cout << tl << ' ' << tr << ' ' << mn[v] << ' ' << mx[v] << ' ' << ok << ' ' << _mn[v] << ' ' << _mx[v] << '\n';
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,ok,v+v,tl,tm);
        upd(l,r,val,ok,v+v+1,tm+1,tr);
        mn[v] = min(mn[v + v], mn[v + v + 1]);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
    }
}
void go(int v = 1,int tl = 1,int tr = _n){
    if(tl == tr){
        res[tl - 1] = mn[v];
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        go(v+v,tl,tm);
        go(v+v+1,tm+1,tr);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    memset(_mn,-1,sizeof(_mn));
    memset(_mx, -1, sizeof(_mx));
    _n = n;
    for(int i = 0;i < k;i++){
        upd(left[i] + 1,right[i] + 1,height[i],(op[i] - 1));
    }
    go();
    for(int i = 0;i < n;i++){
        finalHeight[i] = res[i];
    }
    return;
}
//int main()
//{
//    int n;
//    int k;
//    int i, j;
//    int status = 0;
//    status = scanf("%d%d", &n, &k);
//    assert(status == 2);
//    int* op = (int*)calloc(sizeof(int), k);
//    int* left = (int*)calloc(sizeof(int), k);
//    int* right = (int*)calloc(sizeof(int), k);
//    int* height = (int*)calloc(sizeof(int), k);
//    int* finalHeight = (int*)calloc(sizeof(int), n);
//
//    for (i = 0; i < k; i++){
//        status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
//        assert(status == 4);
//    }
//    buildWall(n, k, op, left, right, height, finalHeight);
//    for (j = 0; j < n; j++)
//        printf("%d\n", finalHeight[j]);
//
//    return 0;
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65884 KB Output is correct
2 Correct 11 ms 66140 KB Output is correct
3 Correct 11 ms 66128 KB Output is correct
4 Correct 16 ms 66396 KB Output is correct
5 Correct 15 ms 66396 KB Output is correct
6 Correct 13 ms 66396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65884 KB Output is correct
2 Correct 109 ms 73720 KB Output is correct
3 Correct 168 ms 69684 KB Output is correct
4 Correct 500 ms 77604 KB Output is correct
5 Correct 218 ms 78192 KB Output is correct
6 Correct 219 ms 78188 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65884 KB Output is correct
2 Correct 12 ms 66140 KB Output is correct
3 Correct 12 ms 66140 KB Output is correct
4 Correct 16 ms 66396 KB Output is correct
5 Correct 15 ms 66396 KB Output is correct
6 Correct 13 ms 66344 KB Output is correct
7 Correct 10 ms 65880 KB Output is correct
8 Correct 111 ms 73888 KB Output is correct
9 Correct 171 ms 69824 KB Output is correct
10 Correct 471 ms 77796 KB Output is correct
11 Correct 226 ms 78064 KB Output is correct
12 Correct 223 ms 78052 KB Output is correct
13 Correct 10 ms 65884 KB Output is correct
14 Correct 120 ms 73812 KB Output is correct
15 Correct 45 ms 66900 KB Output is correct
16 Correct 695 ms 80016 KB Output is correct
17 Correct 243 ms 89108 KB Output is correct
18 Correct 223 ms 86944 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66136 KB Output is correct
2 Correct 10 ms 66136 KB Output is correct
3 Correct 11 ms 66136 KB Output is correct
4 Correct 16 ms 66392 KB Output is correct
5 Correct 13 ms 66552 KB Output is correct
6 Correct 14 ms 66416 KB Output is correct
7 Correct 11 ms 65884 KB Output is correct
8 Correct 110 ms 73776 KB Output is correct
9 Correct 169 ms 69712 KB Output is correct
10 Correct 474 ms 77648 KB Output is correct
11 Correct 241 ms 78192 KB Output is correct
12 Correct 215 ms 78120 KB Output is correct
13 Correct 10 ms 65884 KB Output is correct
14 Correct 113 ms 73756 KB Output is correct
15 Correct 45 ms 67016 KB Output is correct
16 Correct 713 ms 80084 KB Output is correct
17 Correct 230 ms 89120 KB Output is correct
18 Correct 225 ms 86864 KB Output is correct
19 Correct 537 ms 140336 KB Output is correct
20 Correct 539 ms 137760 KB Output is correct
21 Correct 566 ms 143716 KB Output is correct
22 Correct 541 ms 140004 KB Output is correct
23 Correct 534 ms 139964 KB Output is correct
24 Correct 541 ms 141192 KB Output is correct
25 Correct 532 ms 138728 KB Output is correct
26 Correct 553 ms 143700 KB Output is correct
27 Correct 531 ms 143680 KB Output is correct
28 Correct 532 ms 140236 KB Output is correct
29 Correct 533 ms 138644 KB Output is correct
30 Correct 550 ms 138932 KB Output is correct