oj.uz

Submission #420356

# Submission time Handle Problem Language Result Execution time Memory
420356 2021-06-08T10:08:09 Z iulia13 Wall (IOI14_wall) C++14
100 / 100
 911 ms 72356 KB 
#include <iostream>
#include "wall.h"
using namespace std;
const int N = 2e6 + 5;
const int INF = 2e9;
struct Node{
    int minim, maxim;
} seg[4 * N];
void op1(int nod, int val)
{
    seg[nod].minim = min(seg[nod].minim, val);
    seg[nod].maxim = min(val, seg[nod].maxim);
}
void op2(int nod, int val)
{
    seg[nod].maxim = max(seg[nod].maxim, val);
    seg[nod].minim = max(val, seg[nod].minim);
}
void push(int nod)
{
    int ls = 2 * nod, rs = ls + 1;
    op1(ls, seg[nod].minim);
    op1(rs, seg[nod].minim);
    op2(ls, seg[nod].maxim);
    op2(rs, seg[nod].maxim);
}
void update(int nod, int l, int r, int ql, int qr, int val, int tip)
{
    if (l > r || l > qr || r < ql)
        return;
    if (ql <= l && r <= qr)
    {
        if (tip == 2)
            op1(nod, val);
        else
            op2(nod, val);
        return;
    }
    int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
    push(nod);
    seg[nod].maxim = 0;
    seg[nod].minim = INF;
    update(ls, l, mid, ql, qr, val, tip);
    update(rs, mid + 1, r, ql, qr, val, tip);
}
int aa[N];
void query(int nod, int l, int r){
    if(l == r)
    {
        aa[l] = min(seg[nod].maxim, seg[nod].minim);
        return;
    }
    int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
    push(nod);
    seg[nod].maxim = 0;
    seg[nod].minim = INF;
    query(ls, l, mid);
    query(rs, mid + 1, r);
}
void buildWall(int n, int k, int op[], int lft[], int rgt[], int height[], int ans[])
{
    int i;
    for (int h = 0; h < k; h++)
    {
        lft[h]++;
        rgt[h]++;
        update(1, 1, n, lft[h], rgt[h], height[h], op[h]);
    }
    query(1, 1, n);
    for (i = 0; i < n; i++)
        ans[i] = aa[i + 1];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 6 ms 764 KB Output is correct
6 Correct 6 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 154 ms 13200 KB Output is correct
3 Correct 193 ms 8132 KB Output is correct
4 Correct 549 ms 16436 KB Output is correct
5 Correct 364 ms 16944 KB Output is correct
6 Correct 349 ms 16816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 6 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 162 ms 13360 KB Output is correct
9 Correct 194 ms 8136 KB Output is correct
10 Correct 563 ms 16368 KB Output is correct
11 Correct 362 ms 16868 KB Output is correct
12 Correct 343 ms 16904 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 157 ms 13444 KB Output is correct
15 Correct 31 ms 1988 KB Output is correct
16 Correct 550 ms 16656 KB Output is correct
17 Correct 356 ms 16664 KB Output is correct
18 Correct 349 ms 16620 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 844 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 156 ms 13304 KB Output is correct
9 Correct 198 ms 8036 KB Output is correct
10 Correct 600 ms 16452 KB Output is correct
11 Correct 351 ms 16964 KB Output is correct
12 Correct 344 ms 16936 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 180 ms 13268 KB Output is correct
15 Correct 32 ms 2012 KB Output is correct
16 Correct 540 ms 16620 KB Output is correct
17 Correct 350 ms 16560 KB Output is correct
18 Correct 351 ms 16604 KB Output is correct
19 Correct 866 ms 71960 KB Output is correct
20 Correct 838 ms 69436 KB Output is correct
21 Correct 891 ms 72076 KB Output is correct
22 Correct 835 ms 69424 KB Output is correct
23 Correct 897 ms 69356 KB Output is correct
24 Correct 907 ms 69428 KB Output is correct
25 Correct 911 ms 69872 KB Output is correct
26 Correct 848 ms 72356 KB Output is correct
27 Correct 871 ms 72252 KB Output is correct
28 Correct 852 ms 69780 KB Output is correct
29 Correct 854 ms 69724 KB Output is correct
30 Correct 857 ms 69824 KB Output is correct