oj.uz

Submission #30911

# Submission time Handle Problem Language Result Execution time Memory
30911 2017-08-01T04:36:44 Z kajebiii Wall (IOI14_wall) C++14
100 / 100
 1453 ms 205252 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);
    }
    pi merge(pi a, pi b) {
        return pi(min(max(a.one, b.one), b.two), min(max(a.two, b.one), b.two));
    }
    void lazy() {
        if(lp) {
            lp->val = merge(lp->val, val);
            rp->val = merge(rp->val, val);
        }
    }
    void update(int a, int b, pi v) {
        if(b < l || r < a) return;
        lazy();
        if(a <= l && r <= b) {
            val = merge(val, v);
            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 2040 KB Output is correct
2 Correct 0 ms 2176 KB Output is correct
3 Correct 0 ms 2172 KB Output is correct
4 Correct 9 ms 3100 KB Output is correct
5 Correct 6 ms 3100 KB Output is correct
6 Correct 6 ms 3100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 196 ms 9864 KB Output is correct
3 Correct 249 ms 7020 KB Output is correct
4 Correct 843 ms 19628 KB Output is correct
5 Correct 429 ms 19628 KB Output is correct
6 Correct 406 ms 19628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 0 ms 2172 KB Output is correct
4 Correct 6 ms 3100 KB Output is correct
5 Correct 3 ms 3100 KB Output is correct
6 Correct 13 ms 3100 KB Output is correct
7 Correct 0 ms 2040 KB Output is correct
8 Correct 209 ms 9864 KB Output is correct
9 Correct 263 ms 7020 KB Output is correct
10 Correct 846 ms 19628 KB Output is correct
11 Correct 433 ms 19628 KB Output is correct
12 Correct 386 ms 19628 KB Output is correct
13 Correct 0 ms 2040 KB Output is correct
14 Correct 169 ms 9864 KB Output is correct
15 Correct 36 ms 4252 KB Output is correct
16 Correct 813 ms 19628 KB Output is correct
17 Correct 343 ms 19628 KB Output is correct
18 Correct 393 ms 19628 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 0 ms 2172 KB Output is correct
4 Correct 13 ms 3100 KB Output is correct
5 Correct 3 ms 3100 KB Output is correct
6 Correct 6 ms 3100 KB Output is correct
7 Correct 0 ms 2040 KB Output is correct
8 Correct 203 ms 9864 KB Output is correct
9 Correct 269 ms 7020 KB Output is correct
10 Correct 883 ms 19628 KB Output is correct
11 Correct 453 ms 19628 KB Output is correct
12 Correct 373 ms 19628 KB Output is correct
13 Correct 0 ms 2040 KB Output is correct
14 Correct 239 ms 9864 KB Output is correct
15 Correct 46 ms 4252 KB Output is correct
16 Correct 736 ms 19628 KB Output is correct
17 Correct 369 ms 19628 KB Output is correct
18 Correct 336 ms 19628 KB Output is correct
19 Correct 1453 ms 205252 KB Output is correct
20 Correct 1296 ms 205252 KB Output is correct
21 Correct 1336 ms 205252 KB Output is correct
22 Correct 1303 ms 205252 KB Output is correct
23 Correct 1306 ms 205252 KB Output is correct
24 Correct 1283 ms 205252 KB Output is correct
25 Correct 1226 ms 205252 KB Output is correct
26 Correct 1389 ms 205252 KB Output is correct
27 Correct 1339 ms 205252 KB Output is correct
28 Correct 1319 ms 205252 KB Output is correct
29 Correct 1259 ms 205252 KB Output is correct
30 Correct 1316 ms 205252 KB Output is correct