oj.uz

Submission #282486

# Submission time Handle Problem Language Result Execution time Memory
282486 2020-08-24T13:05:16 Z Kastanda Wall (IOI14_wall) C++11
100 / 100
 844 ms 59888 KB 
// M
#include<bits/stdc++.h>
#include "wall.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 2000006, MXS = N * 4, MXH = 1e5 + 3;
int n, MN[MXS], MX[MXS];
int * RS;
inline void Apply(int id, int mn, int mx)
{
        assert(mn >= mx);
        // mn :
        MN[id] = min(MN[id], mn);
        if (MX[id] > MN[id]) MX[id] = mn;
        // mx :
        MX[id] = max(MX[id], mx);
        if (MN[id] < MX[id]) MN[id] = mx;
}
inline void Shift(int id)
{
        Apply(lc, MN[id], MX[id]);
        Apply(rc, MN[id], MX[id]);
        MN[id] = MXH;
        MX[id] = 0;
}
void Add(int le, int ri, int mn, int mx, int id = 1, int l = 0, int r = n)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
                return void(Apply(id, mn, mx));
        Shift(id);
        Add(le, ri, mn, mx, lc, l, md);
        Add(le, ri, mn, mx, rc, md, r);
}
void DFS(int id = 1, int l = 0, int r = n)
{
        if (r - l < 2)
                return void(RS[l] = MX[id]);
        Shift(id);
        DFS(lc, l, md);
        DFS(rc, md, r);
}
void buildWall(int _n, int q, int * op, int * le, int * ri, int * A, int * Rs)
{
        n = _n; RS = Rs;
        for (int i = 0; i < q; i ++)
        {
                if (op[i] == 1)
                        Add(le[i], ri[i] + 1, MXH, A[i]);
                else
                        Add(le[i], ri[i] + 1, A[i], 0);
        }
        DFS();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 202 ms 8432 KB Output is correct
3 Correct 204 ms 4728 KB Output is correct
4 Correct 566 ms 11640 KB Output is correct
5 Correct 349 ms 11896 KB Output is correct
6 Correct 332 ms 12024 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 197 ms 8440 KB Output is correct
9 Correct 209 ms 4600 KB Output is correct
10 Correct 624 ms 11512 KB Output is correct
11 Correct 350 ms 11768 KB Output is correct
12 Correct 341 ms 12152 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 196 ms 8316 KB Output is correct
15 Correct 33 ms 2040 KB Output is correct
16 Correct 545 ms 11640 KB Output is correct
17 Correct 338 ms 11796 KB Output is correct
18 Correct 337 ms 11928 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 187 ms 8312 KB Output is correct
9 Correct 198 ms 4732 KB Output is correct
10 Correct 558 ms 11256 KB Output is correct
11 Correct 354 ms 12004 KB Output is correct
12 Correct 332 ms 12024 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 185 ms 8312 KB Output is correct
15 Correct 32 ms 2168 KB Output is correct
16 Correct 547 ms 11644 KB Output is correct
17 Correct 334 ms 11768 KB Output is correct
18 Correct 335 ms 11896 KB Output is correct
19 Correct 782 ms 59640 KB Output is correct
20 Correct 802 ms 57268 KB Output is correct
21 Correct 844 ms 59888 KB Output is correct
22 Correct 835 ms 57080 KB Output is correct
23 Correct 784 ms 57208 KB Output is correct
24 Correct 793 ms 57252 KB Output is correct
25 Correct 788 ms 57092 KB Output is correct
26 Correct 817 ms 59752 KB Output is correct
27 Correct 790 ms 59768 KB Output is correct
28 Correct 798 ms 57232 KB Output is correct
29 Correct 836 ms 57592 KB Output is correct
30 Correct 782 ms 57420 KB Output is correct