oj.uz

Submission #995643

# Submission time Handle Problem Language Result Execution time Memory
995643 2024-06-09T14:28:18 Z Icelast Wall (IOI14_wall) C++17
0 / 100
 0 ms 348 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++){
        cout << left[i]+1 << " " << right[i]+1 << "\n";
        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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -