oj.uz

Submission #978027

# Submission time Handle Problem Language Result Execution time Memory
978027 2024-05-08T17:07:48 Z shezitt Wall (IOI14_wall) C++14
24 / 100
 271 ms 25660 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define ii pair<int,int>
#define vi vector<int>

struct mxtree {
    vi t;
    vi lazy;
    int n;
    mxtree(int n) : n(n) {
        t.assign(4*n, 0);
        lazy.assign(4*n, 0);
    }
    void update(int i, int tl, int tr, int l, int r, int val){
        if(l <= tl && tr <= r){
            lazy[i] = max(lazy[i], val);
            return;
        }
        if(r < tl or tr < l){
            return;
        }
        int tm = (tl + tr) / 2;
        update(2*i+1, tl, tm, l, r, val);
        update(2*i+2, tm+1, tr, l, r, val);
    }
    void update(int l, int r, int val){
        update(0, 0, n-1, l, r, val);
    }
    void push(int i, int tl, int tr){
        t[i] = max(t[i], lazy[i]);
        lazy[2*i+1] = max(lazy[2*i+1], lazy[i]);
        lazy[2*i+2] = max(lazy[2*i+2], lazy[i]);
        lazy[i] = 0;
    }
    int query(int i, int tl, int tr, int idx){
        if(tl == tr){
            t[i] = max(t[i], lazy[i]);
            return t[i];
        }
        push(i, tl, tr);
        int tm = (tl + tr) / 2;
        if(idx <= tm){
            return query(2*i+1, tl, tm, idx);
        } else {
            return query(2*i+2, tm+1, tr, idx);
        }
    }
    int query(int idx){
        return query(0, 0, n-1, idx);
    }
};

struct mntree {
    vi t;
    vi lazy;
    int n;
    vi arr;
    mntree(int a[], int n) : n(n) {
        arr.assign(n, 0);
        fore(i, 0, n){
            arr[i] = a[i];
        }
        t.assign(4*n, 1e9+7);
        lazy.assign(4*n, 1e9+7);
        init(0, 0, n-1);
    }
    void init(int i, int tl, int tr){
        if(tl == tr){
            t[i] = arr[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        init(2*i+1, tl, tm);
        init(2*i+2, tm+1, tr);
        t[i] = min(t[2*i+1], t[2*i+2]);
    }
    void update(int i, int tl, int tr, int l, int r, int val){
        if(l <= tl && tr <= r){
            lazy[i] = min(lazy[i], val);
            return;
        }
        if(r < tl or tr < l){
            return;
        }
        int tm = (tl + tr) / 2;
        update(2*i+1, tl, tm, l, r, val);
        update(2*i+2, tm+1, tr, l, r, val);
    }
    void update(int l, int r, int val){
        update(0, 0, n-1, l, r, val);
    }
    void push(int i, int tl, int tr){
        t[i] = min(t[i], lazy[i]);
        lazy[2*i+1] = min(lazy[2*i+1], lazy[i]);
        lazy[2*i+2] = min(lazy[2*i+2], lazy[i]);
        lazy[i] = 1e9+7;
    }
    int query(int i, int tl, int tr, int idx){
        if(tl == tr){
            t[i] = min(t[i], lazy[i]);
            return t[i];
        }
        push(i, tl, tr);
        int tm = (tl + tr) / 2;
        if(idx <= tm){
            return query(2*i+1, tl, tm, idx);
        } else {
            return query(2*i+2, tm+1, tr, idx);
        }
    }
    int query(int idx){
        return query(0, 0, n-1, idx);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    mxtree Tmax(n);

    fore(i, 0, k){
        if(op[i] == 2) break;
        Tmax.update(left[i], right[i], height[i]);
    }

    fore(i, 0, n){
        finalHeight[i] = Tmax.query(i);
    }

    mntree Tmin(finalHeight, n);
    vi tmp(n+1);
    fore(i, 0, k){
        if(op[i] == 1) continue;
        Tmin.update(left[i], right[i], height[i]);
        tmp[right[i]+1]--;
        tmp[left[i]]++;
    }

    fore(i, 1, n+1){
        tmp[i] += tmp[i-1];
    }

    fore(i, 0, n){
        if(tmp[i] > 0){
            finalHeight[i] = Tmin.query(i);
        }
    }

    return;
}

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 110 ms 14084 KB Output is correct
3 Correct 146 ms 7504 KB Output is correct
4 Correct 271 ms 25168 KB Output is correct
5 Correct 182 ms 25660 KB Output is correct
6 Correct 173 ms 24044 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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