oj.uz

Submission #30910

# Submission time Handle Problem Language Result Execution time Memory
30910 2017-08-01T04:34:23 Z kajebiii Wall (IOI14_wall) C++14
100 / 100
 1606 ms 205248 KB 
#include "wall.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

struct NODE{
    int l, r; pi val;
    NODE *lp, *rp;

    NODE(int a, int b) : l(a), r(b), val(pi(0, 0)), lp(NULL), rp(NULL) {
        if(a == b) return;
        int m = (a+b) >> 1;
        lp = new NODE(a, m);
        rp = new NODE(m+1, b);
    }
    void lazy() {
        if(lp) {
            lp->val.one = max(lp->val.one, val.one);
            lp->val.two = max(lp->val.two, val.one);
            lp->val.one = min(lp->val.one, val.two);
            lp->val.two = min(lp->val.two, val.two);

            rp->val.one = max(rp->val.one, val.one);
            rp->val.two = max(rp->val.two, val.one);
            rp->val.one = min(rp->val.one, val.two);
            rp->val.two = min(rp->val.two, val.two);
        }
    }
    void update(int a, int b, pi v) {
        if(b < l || r < a) return;
        lazy();
        if(a <= l && r <= b) {
            if(v.one == -INF) {
                val.one = min(val.one, v.two);
                val.two = min(val.two, v.two);
            }else if(v.two == INF) {
                val.one = max(val.one, v.one);
                val.two = max(val.two, v.one);
            }
            return;
        }
        lp->update(a, b, v);
        rp->update(a, b, v);
        val = pi(min(lp->val.one, rp->val.one), max(lp->val.two, rp->val.two));
    }
    int getV(int v) {
        if(v < l || r < v) return -1;
        if(l == r) return val.one;
        lazy();
        int lv = lp->getV(v);
        int rv = rp->getV(v);
        return max(lv, rv);
    }
};

int N, Q;
void buildWall(int n, int k, int opp[], int ll[], int rr[], int hh[], int fh[]){
    N = n; Q = k;
    NODE *root = new NODE(0, N-1);
    for(int q=0; q<Q; q++) {
//        printf("%d start\n", q);
        int o = opp[q], l = ll[q], r = rr[q], h = hh[q];
        pi val = pi(-INF, +INF);
        if(o == 1) val.one = h; else val.two = h;
        root->update(l, r, val);
    }
    for(int i=0; i<N; i++) fh[i] = root->getV(i);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2172 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct
4 Correct 6 ms 3096 KB Output is correct
5 Correct 6 ms 3096 KB Output is correct
6 Correct 3 ms 3096 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 203 ms 9860 KB Output is correct
3 Correct 239 ms 7016 KB Output is correct
4 Correct 853 ms 19624 KB Output is correct
5 Correct 433 ms 19624 KB Output is correct
6 Correct 363 ms 19624 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2172 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct
4 Correct 9 ms 3096 KB Output is correct
5 Correct 6 ms 3096 KB Output is correct
6 Correct 6 ms 3096 KB Output is correct
7 Correct 0 ms 2036 KB Output is correct
8 Correct 199 ms 9860 KB Output is correct
9 Correct 246 ms 7016 KB Output is correct
10 Correct 993 ms 19624 KB Output is correct
11 Correct 366 ms 19624 KB Output is correct
12 Correct 379 ms 19624 KB Output is correct
13 Correct 0 ms 2036 KB Output is correct
14 Correct 176 ms 9860 KB Output is correct
15 Correct 46 ms 4248 KB Output is correct
16 Correct 979 ms 19624 KB Output is correct
17 Correct 406 ms 19624 KB Output is correct
18 Correct 369 ms 19624 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2036 KB Output is correct
2 Correct 0 ms 2172 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct
4 Correct 9 ms 3096 KB Output is correct
5 Correct 0 ms 3096 KB Output is correct
6 Correct 6 ms 3096 KB Output is correct
7 Correct 0 ms 2036 KB Output is correct
8 Correct 189 ms 9860 KB Output is correct
9 Correct 233 ms 7016 KB Output is correct
10 Correct 923 ms 19624 KB Output is correct
11 Correct 439 ms 19624 KB Output is correct
12 Correct 406 ms 19624 KB Output is correct
13 Correct 0 ms 2036 KB Output is correct
14 Correct 193 ms 9860 KB Output is correct
15 Correct 43 ms 4248 KB Output is correct
16 Correct 959 ms 19624 KB Output is correct
17 Correct 486 ms 19624 KB Output is correct
18 Correct 426 ms 19624 KB Output is correct
19 Correct 1416 ms 205248 KB Output is correct
20 Correct 1356 ms 205248 KB Output is correct
21 Correct 1453 ms 205248 KB Output is correct
22 Correct 1526 ms 205248 KB Output is correct
23 Correct 1553 ms 205248 KB Output is correct
24 Correct 1409 ms 205248 KB Output is correct
25 Correct 1513 ms 205248 KB Output is correct
26 Correct 1523 ms 205248 KB Output is correct
27 Correct 1553 ms 205248 KB Output is correct
28 Correct 1606 ms 205248 KB Output is correct
29 Correct 1366 ms 205248 KB Output is correct
30 Correct 1386 ms 205248 KB Output is correct