oj.uz

Submission #697827

# Submission time Handle Problem Language Result Execution time Memory
697827 2023-02-11T07:06:40 Z TheSahib Wall (IOI14_wall) C++14
24 / 100
 574 ms 12368 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9
 
using namespace std;
 
int N;
vector<pii> tree;
vector<bool> lazy;

void push(int node, int l, int r){
    if(!lazy[node]) return;

    if(l != r){
        lazy[node * 2 + 1] = lazy[node * 2 + 2] = 1;

        tree[node * 2 + 1].second = min(tree[node * 2 + 1].second, tree[node].second);
        tree[node * 2 + 1].first = min(tree[node * 2 + 1].first, tree[node * 2 + 1].second);

        tree[node * 2 + 2].second = min(tree[node * 2 + 2].second, tree[node].second);
        tree[node * 2 + 2].first = min(tree[node * 2 + 2].first, tree[node * 2 + 2].second);
        
    }
    lazy[node] = 0;
}
 
void update(int node, int l, int r, int ul, int ur, pii val){
    push(node, l, r);
    if(ur < l || r < ul){ return; }
 
    if(ul <= l && r <= ur){
        if(val.first != -oo){
            tree[node].first = max(tree[node].first, val.first);
            tree[node].second = max(tree[node].second, tree[node].first);
            lazy[node] = 1;
        }
        if(val.second != oo){
            tree[node].second = min(tree[node].second, val.second);
            tree[node].first = min(tree[node].second, tree[node].first);
            lazy[node] = 1;
        }
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2 + 1, l, mid, ul, ur, val);
    update(node * 2 + 2, mid + 1, r, ul, ur, val);
}
 
void ask(int node, int l, int r, int pos, int &ans){
    push(node, l, r);
    ans = max(tree[node].first, ans);
    ans = min(tree[node].second, ans);
    if(l == r){ return; }
    
    int mid = (l + r) / 2;
    if(pos <= mid){
        ask(node * 2 + 1, l, mid, pos, ans);
    }
    else{
        ask(node * 2 + 2, mid + 1, r, pos, ans);
    }
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    tree.resize(N * 4, {0, oo});
    lazy.resize(N * 4, 0);

    for (int i = 0; i < k; i++)
    {
        update(0, 0, N - 1, left[i], right[i], {(op[i] == 1) ? height[i] : -oo, (op[i] == 2) ? height[i] : oo});
    }
    
    for (int i = 0; i < N; i++)
    {
        int a = 0;
        ask(0, 0, N - 1, i, a);
        finalHeight[i] = a;
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 143 ms 8056 KB Output is correct
3 Correct 196 ms 4188 KB Output is correct
4 Correct 574 ms 11828 KB Output is correct
5 Correct 262 ms 12336 KB Output is correct
6 Correct 245 ms 12368 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -