oj.uz

Submission #930530

# Submission time Handle Problem Language Result Execution time Memory
930530 2024-02-20T05:49:23 Z vjudge1 Wall (IOI14_wall) C++17
8 / 100
 3000 ms 74112 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 && tl == tr){
        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 12 ms 65884 KB Output is correct
2 Correct 11 ms 66112 KB Output is correct
3 Correct 12 ms 66140 KB Output is correct
4 Correct 214 ms 66340 KB Output is correct
5 Correct 230 ms 66332 KB Output is correct
6 Correct 214 ms 66332 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65884 KB Output is correct
2 Correct 118 ms 73808 KB Output is correct
3 Execution timed out 3011 ms 69456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66104 KB Output is correct
2 Correct 11 ms 66168 KB Output is correct
3 Correct 12 ms 66140 KB Output is correct
4 Correct 205 ms 66592 KB Output is correct
5 Correct 208 ms 66340 KB Output is correct
6 Correct 206 ms 66348 KB Output is correct
7 Correct 10 ms 65884 KB Output is correct
8 Correct 119 ms 74112 KB Output is correct
9 Execution timed out 3043 ms 69540 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65880 KB Output is correct
2 Correct 10 ms 66136 KB Output is correct
3 Correct 12 ms 66148 KB Output is correct
4 Correct 201 ms 66356 KB Output is correct
5 Correct 219 ms 66336 KB Output is correct
6 Correct 206 ms 66340 KB Output is correct
7 Correct 10 ms 65884 KB Output is correct
8 Correct 117 ms 73728 KB Output is correct
9 Execution timed out 3076 ms 69696 KB Time limit exceeded
10 Halted 0 ms 0 KB -