oj.uz

Submission #1091614

# Submission time Handle Problem Language Result Execution time Memory
1091614 2024-09-21T14:29:54 Z vladilius Wall (IOI14_wall) C++17
0 / 100
 89 ms 14032 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e5;
 
vector<pii> t;
 
void ap1(int v, int& x){
    t[v].ff = max(t[v].ff, x);
    if (t[v].ff > t[v].ss) t[v].ss = t[v].ff;
}
 
void ap2(int v, int& x){
    t[v].ss = min(t[v].ss, x);
    if (t[v].ff > t[v].ss) t[v].ff = t[v].ss;
}
 
void push(int& v){
    int vv = 2 * v;
    ap1(vv, t[v].ff);
    ap1(vv + 1, t[v].ff);
    ap2(vv, t[v].ss);
    ap2(vv + 1, t[v].ss);
    t[v] = {0, inf};
}
 
void chmax(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap1(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmax(vv, tl, tm, l, r, x);
    chmax(vv + 1, tm + 1, tr, l, r, x);
}
 
void chmin(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap2(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmin(vv, tl, tm, l, r, x);
    chmin(vv + 1, tm + 1, tr, l, r, x);
}
 
int f(int x, pii& d){
    return min(max(x, d.ff), d.ss);
}
 
void get(int v, int tl, int tr, int p, int& x){
    x = f(x, t[v]);
    if (tl == tr) return;
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    if (p <= tm){
        get(vv, tl, tm, p, x);
    }
    else {
        get(vv + 1, tm + 1, tr, p, x);
    }
}
 
void buildWall(int n, int k, int type[], int l[], int r[], int h[], int H[]){
    t.assign(4 * n, {0, inf});
    for (int i = k - 1; i >= 0; i--){
        l[i]++; r[i]++;
        if (type[i] == 1){
            chmax(1, 1, n, l[i], r[i], h[i]);
        }
        else {
            chmin(1, 1, n, l[i], r[i], h[i]);
        }
    }
    
    for (int i = 0; i < n; i++) get(1, 1, n, i + 1, H[i]);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 89 ms 14032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -