oj.uz

Submission #930526

# Submission time Handle Problem Language Result Execution time Memory
930526 2024-02-20T05:41:54 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 149 ms 79788 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] = _mn[v] = val;
        }else if(val >= mn[v]){
            mn[v] = _mn[v] = val;
        }
    }else{
        if(val <= mn[v]){
            mn[v] = _mn[v] = _mx[v] = _mn[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){
        pull(v,val,ok);
    }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];
//        assert(mn[v] == mx[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],1 - (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;
//}

Compilation message

wall.cpp: In function 'void pull(int, int, bool)':
wall.cpp:14:28: warning: operation on '_mn[v]' may be undefined [-Wsequence-point]
   14 |             mn[v] = _mn[v] = _mx[v] = _mn[v] = val;
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:20:28: warning: operation on '_mn[v]' may be undefined [-Wsequence-point]
   20 |             mn[v] = _mn[v] = _mx[v] = _mn[v] = val;
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66032 KB Output is correct
2 Correct 10 ms 66252 KB Output is correct
3 Incorrect 10 ms 65992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65992 KB Output is correct
2 Correct 117 ms 79788 KB Output is correct
3 Incorrect 149 ms 72188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66076 KB Output is correct
2 Correct 11 ms 66256 KB Output is correct
3 Incorrect 10 ms 66140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65884 KB Output is correct
2 Correct 10 ms 66124 KB Output is correct
3 Incorrect 11 ms 66036 KB Output isn't correct
4 Halted 0 ms 0 KB -