oj.uz

Submission #996001

# Submission time Handle Problem Language Result Execution time Memory
996001 2024-06-10T06:58:17 Z Icelast Wall (IOI14_wall) C++17
100 / 100
 1326 ms 92244 KB 
#include "wall.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
struct SegmentTree{
    struct Node{
        ll chmn, chmx;
    };
    ll n, N;
    vector<Node> T;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, {INF, -INF});
    };
    Node combine(Node a, Node b){
        if(b.chmn >= a.chmn){
            //nothing changed
        }else if(b.chmn >= a.chmx && b.chmn < a.chmn){
            a.chmn = b.chmn;
        }else if(b.chmn < a.chmx){
            a.chmn = b.chmn;
            a.chmx = b.chmn;
        }
        if(b.chmx >= a.chmn){
            a.chmn = b.chmx;
            a.chmx = b.chmx;
        }else if(b.chmx >= a.chmx && b.chmx < a.chmn){
            a.chmx = b.chmx;
        }else if(b.chmx < a.chmx){
            //nothing changed;
        }
        return a;
    }
    void down(int node){
        for(int child = node*2; child <= node*2+1; child++){
            if(child >= 2*N) return;
            T[child] = combine(T[child], T[node]);
        }
        T[node] = {INF, -INF};
    }
    void upd(int l, int r, int ch, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int l, int r, int ch, ll x) -> void{
            down(node);
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                Node X;
                if(ch == 1){
                    X = {INF, x};
                }else{
                    X = {x, -INF};
                }
                T[node] = combine(T[node], X);
                down(node);
                return;
            }
            int mid = (low+high)/2;
            upd(upd, node*2, low, mid, l, r, ch, x);
            upd(upd, node*2+1, mid+1, high, l, r, ch, x);
        };
        upd(upd, 1, 1, N, l, r, ch, x);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree T(n+5);
    for(int i = 0; i < k; i++){
        T.upd(left[i]+1, right[i]+1, op[i], height[i]);
    }
    for(int i = 1; i <= n; i++){
        T.upd(i, i, 1, -INF);
    }
    for(int i = 1; i <= n; i++){
        ll val = 0;
        val = min(val, T.T[i+T.N-1].chmn);
        val = max(val, T.T[i+T.N-1].chmx);
        finalHeight[i-1] = val;
    }
    return;
}

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 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 121 ms 14068 KB Output is correct
3 Correct 165 ms 7248 KB Output is correct
4 Correct 559 ms 22232 KB Output is correct
5 Correct 272 ms 22848 KB Output is correct
6 Correct 277 ms 21156 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1148 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 103 ms 13908 KB Output is correct
9 Correct 163 ms 8528 KB Output is correct
10 Correct 546 ms 22352 KB Output is correct
11 Correct 284 ms 22864 KB Output is correct
12 Correct 315 ms 21272 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 108 ms 14048 KB Output is correct
15 Correct 34 ms 2528 KB Output is correct
16 Correct 575 ms 22288 KB Output is correct
17 Correct 293 ms 21572 KB Output is correct
18 Correct 281 ms 21584 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 7 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 105 ms 13908 KB Output is correct
9 Correct 164 ms 8544 KB Output is correct
10 Correct 563 ms 22352 KB Output is correct
11 Correct 275 ms 22864 KB Output is correct
12 Correct 263 ms 21328 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 109 ms 13908 KB Output is correct
15 Correct 34 ms 2392 KB Output is correct
16 Correct 610 ms 22148 KB Output is correct
17 Correct 284 ms 21736 KB Output is correct
18 Correct 274 ms 21560 KB Output is correct
19 Correct 1235 ms 91988 KB Output is correct
20 Correct 1326 ms 91984 KB Output is correct
21 Correct 1273 ms 91960 KB Output is correct
22 Correct 1190 ms 92044 KB Output is correct
23 Correct 1194 ms 91948 KB Output is correct
24 Correct 1199 ms 91984 KB Output is correct
25 Correct 1216 ms 91984 KB Output is correct
26 Correct 1188 ms 92072 KB Output is correct
27 Correct 1223 ms 92244 KB Output is correct
28 Correct 1206 ms 92040 KB Output is correct
29 Correct 1190 ms 92168 KB Output is correct
30 Correct 1208 ms 92040 KB Output is correct