oj.uz

Submission #1073743

# Submission time Handle Problem Language Result Execution time Memory
1073743 2024-08-24T19:48:46 Z shezitt Meetings (IOI18_meetings) C++14
0 / 100
 5500 ms 2904 KB 
#include <bits/stdc++.h>
#include "meetings.h"

using ll = long long;

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

using namespace std;

struct segtree {
    int n;
    vector<ll> T;
    segtree(int n) : n(n) {
        T.assign(4*n+2, 0);
    }

    void update(int i, int tl, int tr, int idx, int val){
        if(tl == tr){
            T[i] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if(idx <= tm){
            update(2*i+1, tl, tm, idx, val);
        } else {
            update(2*i+2, tm+1, tr, idx, val);
        }
        T[i] = max(T[2*i+1], T[2*i+2]);
    }
    void update(int idx, int val){
        update(0, 0, n-1, idx, val);
    }

    ll query(int i, int tl, int tr, int l, int r){
        if(l <= tl && tr <= r){
            return T[i];
        }  
        if(r < tl or tr < l){
            return 0;
        }
        int tm = (tl + tr) / 2;
        ll p1 = query(2*i+1, tl, tm, l, r);
        ll p2 = query(2*i+2, tm+1, tr, l, r);
        return max(p1, p2);
    }
    ll query(int l, int r){
        return query(0, 0, n-1, min(l,r), max(l,r));
    }

};

std::vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int Q = L.size();
    vector<ll> C(Q);

    int N = 0;

    for (int j = 0; j < Q; ++j) {
        N = max(N, R[j]);
    }

    N++;
    assert(N<=3000);

    segtree T(N);
    for(int i=0; i<N; ++i){
        T.update(i, H[i]);
    }

    for(int j=0; j<Q; ++j){
        int l = L[j], r = R[j];

        ll ans = 4e18;
        for(int x=l; x<=r; ++x){
            ll cur = 0;
            for(int i=l; i<=r; ++i){
                cur += T.query(i, x);
            }
            ans = min(ans, cur);
        }

        C[j] = ans;

    }

  
    return C;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1006 ms 524 KB Output is correct
3 Execution timed out 5553 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1006 ms 524 KB Output is correct
3 Execution timed out 5553 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 8 ms 2904 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 8 ms 2904 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1006 ms 524 KB Output is correct
3 Execution timed out 5553 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -