oj.uz

Submission #930543

# Submission time Handle Problem Language Result Execution time Memory
930543 2024-02-20T05:58:10 Z dimashhh Wall (IOI14_wall) C++17
100 / 100
 689 ms 138804 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 11 ms 65884 KB Output is correct
2 Correct 11 ms 66140 KB Output is correct
3 Correct 12 ms 66064 KB Output is correct
4 Correct 17 ms 66396 KB Output is correct
5 Correct 13 ms 66396 KB Output is correct
6 Correct 14 ms 66420 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66000 KB Output is correct
2 Correct 115 ms 73740 KB Output is correct
3 Correct 179 ms 69676 KB Output is correct
4 Correct 534 ms 77792 KB Output is correct
5 Correct 219 ms 78416 KB Output is correct
6 Correct 220 ms 78048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65880 KB Output is correct
2 Correct 11 ms 66392 KB Output is correct
3 Correct 13 ms 66140 KB Output is correct
4 Correct 17 ms 66396 KB Output is correct
5 Correct 13 ms 66396 KB Output is correct
6 Correct 14 ms 66396 KB Output is correct
7 Correct 11 ms 65884 KB Output is correct
8 Correct 122 ms 73740 KB Output is correct
9 Correct 187 ms 69668 KB Output is correct
10 Correct 499 ms 77700 KB Output is correct
11 Correct 227 ms 78092 KB Output is correct
12 Correct 212 ms 78164 KB Output is correct
13 Correct 10 ms 65884 KB Output is correct
14 Correct 113 ms 73900 KB Output is correct
15 Correct 46 ms 66904 KB Output is correct
16 Correct 689 ms 80308 KB Output is correct
17 Correct 227 ms 84784 KB Output is correct
18 Correct 221 ms 82768 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65880 KB Output is correct
2 Correct 11 ms 66140 KB Output is correct
3 Correct 12 ms 66028 KB Output is correct
4 Correct 16 ms 66396 KB Output is correct
5 Correct 14 ms 66368 KB Output is correct
6 Correct 13 ms 66396 KB Output is correct
7 Correct 10 ms 65884 KB Output is correct
8 Correct 116 ms 74112 KB Output is correct
9 Correct 169 ms 69712 KB Output is correct
10 Correct 471 ms 77664 KB Output is correct
11 Correct 217 ms 78164 KB Output is correct
12 Correct 211 ms 78160 KB Output is correct
13 Correct 10 ms 65884 KB Output is correct
14 Correct 158 ms 73868 KB Output is correct
15 Correct 46 ms 66900 KB Output is correct
16 Correct 685 ms 79956 KB Output is correct
17 Correct 225 ms 84816 KB Output is correct
18 Correct 220 ms 82912 KB Output is correct
19 Correct 537 ms 135504 KB Output is correct
20 Correct 527 ms 132464 KB Output is correct
21 Correct 537 ms 138516 KB Output is correct
22 Correct 534 ms 135240 KB Output is correct
23 Correct 535 ms 135464 KB Output is correct
24 Correct 541 ms 136180 KB Output is correct
25 Correct 537 ms 133716 KB Output is correct
26 Correct 532 ms 138804 KB Output is correct
27 Correct 531 ms 138604 KB Output is correct
28 Correct 522 ms 134880 KB Output is correct
29 Correct 516 ms 133456 KB Output is correct
30 Correct 519 ms 133540 KB Output is correct