oj.uz

Submission #1091618

# Submission time Handle Problem Language Result Execution time Memory
1091618 2024-09-21T14:34:28 Z vladilius Wall (IOI14_wall) C++17
100 / 100
 877 ms 99160 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e5;
 
vector<pii> t;
 
void ap1(int v, int& x){
    t[v].ff = max(t[v].ff, x);
    if (t[v].ff > t[v].ss) t[v].ss = t[v].ff;
}
 
void ap2(int v, int& x){
    t[v].ss = min(t[v].ss, x);
    if (t[v].ff > t[v].ss) t[v].ff = t[v].ss;
}
 
void push(int& v){
    int vv = 2 * v;
    ap1(vv, t[v].ff);
    ap1(vv + 1, t[v].ff);
    ap2(vv, t[v].ss);
    ap2(vv + 1, t[v].ss);
    t[v] = {0, inf};
}
 
void chmax(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap1(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmax(vv, tl, tm, l, r, x);
    chmax(vv + 1, tm + 1, tr, l, r, x);
}
 
void chmin(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap2(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmin(vv, tl, tm, l, r, x);
    chmin(vv + 1, tm + 1, tr, l, r, x);
}
 
int f(int x, pii& d){
    return min(max(x, d.ff), d.ss);
}
 
void get(int v, int tl, int tr, int p, int& x){
    if (tl == tr){
    	x = f(x, t[v]);
      	return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    if (p <= tm){
        get(vv, tl, tm, p, x);
    }
    else {
        get(vv + 1, tm + 1, tr, p, x);
    }
}
 
void buildWall(int n, int k, int type[], int l[], int r[], int h[], int H[]){
    t.assign(4 * n, {0, inf});
    for (int i = 0; i < k; i++){
        l[i]++; r[i]++;
        if (type[i] == 1){
            chmax(1, 1, n, l[i], r[i], h[i]);
        }
        else {
            chmin(1, 1, n, l[i], r[i], h[i]);
        }
    }
    
    for (int i = 0; i < n; i++) get(1, 1, n, i + 1, H[i]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 4 ms 964 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 89 ms 8128 KB Output is correct
3 Correct 142 ms 7964 KB Output is correct
4 Correct 368 ms 21584 KB Output is correct
5 Correct 225 ms 22516 KB Output is correct
6 Correct 233 ms 20820 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 892 KB Output is correct
5 Correct 5 ms 960 KB Output is correct
6 Correct 5 ms 964 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 14008 KB Output is correct
9 Correct 136 ms 8020 KB Output is correct
10 Correct 368 ms 21516 KB Output is correct
11 Correct 225 ms 22436 KB Output is correct
12 Correct 212 ms 21072 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 86 ms 13908 KB Output is correct
15 Correct 27 ms 2128 KB Output is correct
16 Correct 465 ms 21640 KB Output is correct
17 Correct 226 ms 21164 KB Output is correct
18 Correct 230 ms 21104 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13824 KB Output is correct
9 Correct 125 ms 7996 KB Output is correct
10 Correct 367 ms 21332 KB Output is correct
11 Correct 220 ms 22356 KB Output is correct
12 Correct 222 ms 20760 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 95 ms 13932 KB Output is correct
15 Correct 32 ms 2132 KB Output is correct
16 Correct 483 ms 21548 KB Output is correct
17 Correct 232 ms 21076 KB Output is correct
18 Correct 228 ms 21072 KB Output is correct
19 Correct 815 ms 99152 KB Output is correct
20 Correct 849 ms 96720 KB Output is correct
21 Correct 823 ms 99048 KB Output is correct
22 Correct 798 ms 96856 KB Output is correct
23 Correct 837 ms 96716 KB Output is correct
24 Correct 842 ms 96592 KB Output is correct
25 Correct 877 ms 96568 KB Output is correct
26 Correct 811 ms 99152 KB Output is correct
27 Correct 819 ms 99160 KB Output is correct
28 Correct 849 ms 96596 KB Output is correct
29 Correct 851 ms 96592 KB Output is correct
30 Correct 847 ms 96592 KB Output is correct