oj.uz

Submission #720405

# Submission time Handle Problem Language Result Execution time Memory
720405 2023-04-08T07:49:40 Z RandomLB Wall (IOI14_wall) C++17
100 / 100
 798 ms 107176 KB 
#include "wall.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef complex<ld> P;
#define ms(x, a) memset(x, a, sizeof(x))
#define siz(x) (int)x.size()
#define len(x) (int)x.length()
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lzMx first
#define lzMn second
#define FOR(i,x) for (int i = 0; i < x; i++)
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vals, Args&&... values){
    cout << vals << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
//===========================================
const int MAX = 8e6+5;
pi st[MAX];
int res[MAX];

inline void chmax(int &a, int b){ a = max(a, b); }
inline void chmin(int &a, int b){ a = min(a, b); }

void prop(int i){
    for (int t = 2*i; t <= 2*i+1; t++){
        if (st[t].lzMx > st[i].lzMn) st[t] = {st[i].lzMn, st[i].lzMn};
        else if (st[t].lzMn < st[i].lzMx) st[t] = {st[i].lzMx, st[i].lzMx};
        else { chmax(st[t].lzMx, st[i].lzMx); chmin(st[t].lzMn, st[i].lzMn); }
    }
    st[i] = {0, INF};
}

void update(int i, int l, int r, int tl, int tr, int val, int c){
    if (l != r) prop(i);
    if (l > tr || r < tl) return;
    if (tl <= l && r <= tr){
       if (c == 1){ chmax(st[i].lzMx, val); chmax(st[i].lzMn, val); }
       else { chmin(st[i].lzMn, val); chmin(st[i].lzMx, val); }
       if (l != r) prop(i);
       return;
    }
    int m = l+(r-l)/2;
    update(2*i, l, m, tl, tr, val, c);
    update(2*i+1, m+1, r, tl, tr, val, c);
}

void walk(int i, int l, int r){
    if (l != r) prop(i);
    if (l == r){ res[l] = st[i].lzMx; return; }
    int m = l+(r-l)/2;
    walk(2*i, l, m); walk(2*i+1, m+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < MAX; i++) st[i] = {0, INF};
    for (int i = 0; i < k; i++){
        left[i]++, right[i]++;
        update(1, 1, n, left[i], right[i], height[i], op[i]);
    }
    walk(1, 1, n);
    for (int i = 0; i < n; i++) finalHeight[i] = res[i+1];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62852 KB Output is correct
2 Correct 26 ms 62972 KB Output is correct
3 Correct 25 ms 62996 KB Output is correct
4 Correct 31 ms 63200 KB Output is correct
5 Correct 28 ms 63144 KB Output is correct
6 Correct 28 ms 63104 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62796 KB Output is correct
2 Correct 171 ms 76460 KB Output is correct
3 Correct 218 ms 70152 KB Output is correct
4 Correct 541 ms 78776 KB Output is correct
5 Correct 361 ms 79360 KB Output is correct
6 Correct 333 ms 79308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62832 KB Output is correct
2 Correct 27 ms 62932 KB Output is correct
3 Correct 24 ms 62940 KB Output is correct
4 Correct 30 ms 63196 KB Output is correct
5 Correct 33 ms 63164 KB Output is correct
6 Correct 30 ms 63296 KB Output is correct
7 Correct 28 ms 62864 KB Output is correct
8 Correct 160 ms 76480 KB Output is correct
9 Correct 202 ms 70096 KB Output is correct
10 Correct 514 ms 78932 KB Output is correct
11 Correct 353 ms 79380 KB Output is correct
12 Correct 343 ms 79236 KB Output is correct
13 Correct 23 ms 62932 KB Output is correct
14 Correct 163 ms 76532 KB Output is correct
15 Correct 55 ms 64100 KB Output is correct
16 Correct 693 ms 79024 KB Output is correct
17 Correct 360 ms 79004 KB Output is correct
18 Correct 350 ms 79044 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62796 KB Output is correct
2 Correct 25 ms 62976 KB Output is correct
3 Correct 26 ms 62956 KB Output is correct
4 Correct 29 ms 63212 KB Output is correct
5 Correct 32 ms 63196 KB Output is correct
6 Correct 29 ms 63180 KB Output is correct
7 Correct 23 ms 62820 KB Output is correct
8 Correct 160 ms 76540 KB Output is correct
9 Correct 201 ms 70056 KB Output is correct
10 Correct 514 ms 78964 KB Output is correct
11 Correct 372 ms 79284 KB Output is correct
12 Correct 340 ms 79288 KB Output is correct
13 Correct 24 ms 62932 KB Output is correct
14 Correct 166 ms 76492 KB Output is correct
15 Correct 57 ms 64204 KB Output is correct
16 Correct 665 ms 79024 KB Output is correct
17 Correct 359 ms 79052 KB Output is correct
18 Correct 360 ms 79132 KB Output is correct
19 Correct 792 ms 107120 KB Output is correct
20 Correct 786 ms 104620 KB Output is correct
21 Correct 793 ms 107176 KB Output is correct
22 Correct 764 ms 104648 KB Output is correct
23 Correct 795 ms 104632 KB Output is correct
24 Correct 758 ms 104612 KB Output is correct
25 Correct 770 ms 104652 KB Output is correct
26 Correct 781 ms 107056 KB Output is correct
27 Correct 789 ms 107084 KB Output is correct
28 Correct 798 ms 104616 KB Output is correct
29 Correct 761 ms 104736 KB Output is correct
30 Correct 756 ms 104628 KB Output is correct