oj.uz

Submission #978170

# Submission time Handle Problem Language Result Execution time Memory
978170 2024-05-09T01:42:42 Z shezitt Wall (IOI14_wall) C++14
0 / 100
 1694 ms 262144 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 segtree {
    vi t;
    int n;
    vector<set<array<int,3>>> lazy;

    segtree(int n) : n(n) {
        t.assign(4*n, 0);
        lazy.assign(4*n, {});
    }

    void updateMx(int i, int tl, int tr, int l, int r, int val, int id){
        if(l <= tl && tr <= r){
            lazy[i].insert({id, 1, val});
            return;
        }
        if(r < tl or tr < l){
            return;
        }
        int tm = (tl + tr) / 2;
        updateMx(2*i+1, tl, tm, l, r, val, id);
        updateMx(2*i+2, tm+1, tr, l, r, val, id);
    }

    void updateMx(int l, int r, int val, int id){
        updateMx(0, 0, n-1, l, r, val, id);
    }

    void updateMn(int i, int tl, int tr, int l, int r, int val, int id){
        if(l <= tl && tr <= r){
            lazy[i].insert({id, 2, val});
            return;
        }
        if(r < tl or tr < l){
            return;
        }
        int tm = (tl + tr) / 2;
        updateMn(2*i+1, tl, tm, l, r, val, id);
        updateMn(2*i+2, tm+1, tr, l, r, val, id);
    }

    void updateMn(int l, int r, int val, int id){
        updateMn(0, 0, n-1, l, r, val, id);
    }

    void push(int i, int tl, int tr){
        if(sz(lazy[i]) == 0) return;
        lazy[2*i+1].insert(all(lazy[i]));
        lazy[2*i+2].insert(all(lazy[i]));
        lazy[i].clear();
    }

    int query(int i, int tl, int tr, int idx){
        if(tl == tr){
            for(auto [id, type, val] : lazy[i]){
                if(type == 1){
                    t[i] = max(t[i], val);
                } else {
                    t[i] = min(t[i], val);
                }
            }
            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[]){

    segtree T(n);

    fore(i, 0, k){
        if(op[i] == 1){
            T.updateMx(left[i], right[i], height[i], i);
        } else {
            T.updateMn(left[i], right[i], height[i], i);
        }
    }

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

    return;
}

Compilation message

wall.cpp: In member function 'int segtree::query(int, int, int, int)':
wall.cpp:65:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |             for(auto [id, type, val] : lazy[i]){
      |                      ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 48 ms 11164 KB Output is correct
4 Runtime error 644 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 213 ms 39496 KB Output is correct
3 Runtime error 1694 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 43 ms 11056 KB Output is correct
4 Runtime error 649 ms 262144 KB Execution killed with signal 9
5 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 Correct 2 ms 600 KB Output is correct
3 Correct 43 ms 10980 KB Output is correct
4 Runtime error 657 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -