oj.uz

답안 #362620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362620 2021-02-03T17:57:22 Z ngpin04 벽 (IOI14_wall) C++14
100 / 100
 1557 ms 69612 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
const int N = 2e6 + 5;
 
pair <int, int> st[4 * N];
 
int ans[N];
int op[N];
int l[N];
int r[N];
int h[N];
int n,k;
 
void dolazy(int id)
{
 
    for (int i = (id << 1); i <= (id << 1 | 1); i++)
    {
        st[i].fi = max(st[i].fi, st[id].fi);
        st[i].se = min(st[i].se, st[id].se);
 
        if (st[i].fi > st[i].se)
        {
            if (st[i].fi == st[id].fi)
                st[i].se = st[i].fi;
            else
                st[i].fi = st[i].se;
        }
    }
}
 
void update(int id, int l, int r, int u, int v, int val, int op)
{
    if (l > v || r < u)
        return;
    if (l >= u && r <= v)
    {
        if (op == 1)
        {
            st[id].fi = max(st[id].fi, val);
            if (st[id].fi > st[id].se)
                st[id].se = st[id].fi;
        } else {
            st[id].se = min(st[id].se, val);
            if (st[id].fi > st[id].se)
                st[id].fi = st[id].se;
        }
        return;
    }
    int mid = (l + r) >> 1;
    dolazy(id);
    update(id << 1, l, mid, u, v, val, op);
    update(id << 1 | 1, mid + 1, r, u, v, val, op);
    st[id].fi = min(st[id << 1].fi, st[id << 1 | 1].fi);
    st[id].se = max(st[id << 1].se, st[id << 1 | 1].se);
}
 
int getval(int id, int l, int r, int pos)
{
    if (l > pos || r < pos)
        return -1;
    if (l == r)
        return st[id].fi;
    int mid = (l + r) >> 1;
    dolazy(id);
    int lnode = getval(id << 1, l, mid, pos);
    int rnode = getval(id << 1 | 1, mid + 1, r, pos);
    return max(lnode, rnode);
}
 
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[])
{
    for (int i = 0; i < k; i++)
        update(1, 1, n, l[i] + 1, r[i] + 1, h[i], op[i]);
 
    for (int i = 1; i <= n; i++)
        ans[i - 1] = getval(1, 1, n, i);
 
    /**for (int i = 0; i < n; i++)
        cerr << ans[i] << endl;*/
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 12 ms 876 KB Output is correct
5 Correct 8 ms 876 KB Output is correct
6 Correct 8 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 156 ms 8684 KB Output is correct
3 Correct 210 ms 4972 KB Output is correct
4 Correct 601 ms 11372 KB Output is correct
5 Correct 429 ms 11756 KB Output is correct
6 Correct 398 ms 11880 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 876 KB Output is correct
5 Correct 8 ms 876 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 155 ms 8684 KB Output is correct
9 Correct 203 ms 4844 KB Output is correct
10 Correct 625 ms 11188 KB Output is correct
11 Correct 405 ms 11756 KB Output is correct
12 Correct 414 ms 11756 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 8684 KB Output is correct
15 Correct 40 ms 2028 KB Output is correct
16 Correct 700 ms 11500 KB Output is correct
17 Correct 414 ms 11500 KB Output is correct
18 Correct 418 ms 11500 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 876 KB Output is correct
5 Correct 8 ms 876 KB Output is correct
6 Correct 8 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 156 ms 8684 KB Output is correct
9 Correct 208 ms 4972 KB Output is correct
10 Correct 616 ms 11244 KB Output is correct
11 Correct 416 ms 11884 KB Output is correct
12 Correct 400 ms 11628 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 159 ms 8556 KB Output is correct
15 Correct 40 ms 2028 KB Output is correct
16 Correct 695 ms 11244 KB Output is correct
17 Correct 408 ms 11116 KB Output is correct
18 Correct 415 ms 11116 KB Output is correct
19 Correct 1539 ms 59088 KB Output is correct
20 Correct 1553 ms 67244 KB Output is correct
21 Correct 1557 ms 69548 KB Output is correct
22 Correct 1533 ms 67076 KB Output is correct
23 Correct 1541 ms 67204 KB Output is correct
24 Correct 1533 ms 67052 KB Output is correct
25 Correct 1536 ms 67052 KB Output is correct
26 Correct 1549 ms 69612 KB Output is correct
27 Correct 1552 ms 69612 KB Output is correct
28 Correct 1545 ms 67052 KB Output is correct
29 Correct 1527 ms 67180 KB Output is correct
30 Correct 1543 ms 67180 KB Output is correct