oj.uz

Submission #727186

# Submission time Handle Problem Language Result Execution time Memory
727186 2023-04-20T07:34:03 Z hoainiem Wall (IOI14_wall) C++14
0 / 100
 168 ms 13828 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc id<<1
#define rc id<<1^1
#define nmax 108
const int inf = 1e6;
using namespace std;
typedef pair<int, int> pii;
pii operator+(pii x, int y){
    return (x.fi < y) ? make_pair(y, x.fi) : ((x.fi > y && y > x.se) ? make_pair(x.fi, y) : x);
}
pii operator-(pii x, int y){
    return (x.fi > y) ? make_pair(y, x.fi) : ((x.fi < y && y < x.se) ? make_pair(x.fi, y) : x);
}
pii operator+(pii x, pii y){
    return (x + y.fi) + y.se;
}
pii operator-(pii x, pii y){
    return (x - y.fi) - y.se;
}
int N, ans[nmax];
struct segmenttrebeats{
    pii mi[nmax << 2], ma[nmax << 2];
    int lazi[nmax << 2];
    void build(int id = 1, int l = 0, int r = N - 1){
        lazi[id] = -1;
        if (l == r){
            mi[id] = {0, inf};
            ma[id] = {0, -inf};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void down(int id){
        mi[lc] = mi[rc] = {lazi[id], inf};
        ma[lc] = ma[rc] = {lazi[id], -inf};
        lazi[lc] = lazi[rc] = lazi[id];
        lazi[id] = -1;
        return;
    }
    void upd_max(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || mi[id].fi >= k)
            return;
        if ((u <= l && r <= v) && (ma[id].fi <= k || mi[id].se == inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_max(u, v, k, lc, l, mid);
        upd_max(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void upd_min(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
        if (r < u || l > v || k >= ma[id].fi)
            return;
        if ((u <= l && r <= v) && (mi[id].fi >= k || ma[id].se == -inf)){
            mi[id] = {k, inf};
            ma[id] = {k, -inf};
            lazi[id] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        upd_min(u, v, k, lc, l, mid);
        upd_min(u, v, k, rc, mid + 1, r);
        mi[id] = mi[lc] - mi[rc];
        ma[id] = ma[lc] + ma[rc];
    }
    void dfs(int id = 1, int l = 0, int r = N - 1){
        if (l == r){
            ans[l] = mi[id].fi;
            return;
        }
        int mid = (l + r) >> 1;
        if (lazi[id] != -1)
            down(id);
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
}tree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    tree.build();
    for (int i = 0; i < k; i++){
        if (op[i] == 1)
            tree.upd_max(left[i], right[i], height[i]);
        else
            tree.upd_min(left[i], right[i], height[i]);
    }
    tree.dfs();
    for (int i = 0; i < n; i++)
        finalHeight[i] = ans[i];
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 168 ms 13828 KB Output is correct
3 Runtime error 67 ms 10956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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