oj.uz

Submission #1085099

# Submission time Handle Problem Language Result Execution time Memory
1085099 2024-09-07T13:59:05 Z BLOBVISGOD Wall (IOI14_wall) C++17
100 / 100
 520 ms 67400 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int oo = 1e9;

struct segtree{
    struct node{
        int lo=-oo, hi=oo;
        void operator+=(node b){
            if (b.hi <= lo) lo=b.hi,hi=b.hi;
            else if (b.lo >= hi) hi = b.lo, lo = b.lo;
            else lo = max(lo,b.lo), hi = min(hi,b.hi);
        }
    };
    int n;
    vector<node> seg;

    segtree(int N){
        n = 1;
        while(n<N) n*= 2;
        seg.resize(n*2);
    }

    void push(int id){
        seg[id*2] += seg[id];
        seg[id*2+1] += seg[id];
        seg[id] = {};
    }

    void upd(int id, int l, int r, int ql, int qr, node u){
        if (l >= qr or r <= ql) return;
        if (l >= ql and r <= qr) return void(seg[id] += u);
        int mid = (l+r)/2;
        push(id);
        upd(id*2,l,mid,ql,qr,u);
        upd(id*2+1,mid,r,ql,qr,u);
    }

    void update(int l, int r, node u){
        upd(1,0,n,l,r,u);
    }

    node& operator[](int id){
        return seg[id+n];
    }

    void finish(){
        rep(i,1,n) push(i);
    }
};

void buildWall(int n, int k, int* op, int* L, int* R, int* H, int* fh){
    cin.tie(NULL),cin.sync_with_stdio(false);

    segtree seg(n);
    rep(i,0,k){
        int  t = op[i], l = L[i], r = R[i], h = H[i];
        if (t==1) seg.update(l,r+1,{h,oo});
        else seg.update(l,r+1,{-oo,h});
    }

    seg.finish();

    vi sol(n);
    rep(i,0,n){
        sol[i] = max(sol[i],seg[i].lo);
        sol[i] = min(sol[i],seg[i].hi);
    }

    rep(i,0,n) fh[i] = sol[i];

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 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 83 ms 14012 KB Output is correct
3 Correct 107 ms 8016 KB Output is correct
4 Correct 295 ms 20560 KB Output is correct
5 Correct 179 ms 21072 KB Output is correct
6 Correct 175 ms 19828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 14104 KB Output is correct
9 Correct 110 ms 8020 KB Output is correct
10 Correct 294 ms 20544 KB Output is correct
11 Correct 189 ms 21072 KB Output is correct
12 Correct 173 ms 19540 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 13924 KB Output is correct
15 Correct 21 ms 2044 KB Output is correct
16 Correct 398 ms 20560 KB Output is correct
17 Correct 196 ms 20048 KB Output is correct
18 Correct 182 ms 19948 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 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 936 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 83 ms 14004 KB Output is correct
9 Correct 107 ms 8020 KB Output is correct
10 Correct 315 ms 20560 KB Output is correct
11 Correct 196 ms 21072 KB Output is correct
12 Correct 181 ms 19536 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 85 ms 13916 KB Output is correct
15 Correct 22 ms 2128 KB Output is correct
16 Correct 397 ms 20504 KB Output is correct
17 Correct 181 ms 20052 KB Output is correct
18 Correct 184 ms 20048 KB Output is correct
19 Correct 426 ms 67192 KB Output is correct
20 Correct 451 ms 67156 KB Output is correct
21 Correct 464 ms 66980 KB Output is correct
22 Correct 449 ms 67152 KB Output is correct
23 Correct 424 ms 67152 KB Output is correct
24 Correct 420 ms 67184 KB Output is correct
25 Correct 428 ms 67136 KB Output is correct
26 Correct 421 ms 67008 KB Output is correct
27 Correct 454 ms 67132 KB Output is correct
28 Correct 424 ms 67400 KB Output is correct
29 Correct 436 ms 67156 KB Output is correct
30 Correct 520 ms 67068 KB Output is correct