oj.uz

Submission #609528

# Submission time Handle Problem Language Result Execution time Memory
609528 2022-07-27T16:53:30 Z MohamedAliSaidane Meetings (IOI18_meetings) C++14
19 / 100
 2987 ms 786432 KB 
#include <bits/stdc++.h>
#include "meetings.h"
    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const ll INF = 1e18;

    const int nax =  1e5 + 4;
    ll sp[nax][20], A[nax];
    int LG[nax];
    int n, q;
    void build()
    {
        for(int i = 0 ; i < n; i++)
            sp[i][0] = A[i];
        for(int j = 1; j < 20; j ++)
            for(int i = 0 ; i + (1 << j) <= n; i ++)
                sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j-1))][j - 1]);
    }
    ll rmq(int l, int r)
    {
        if(l > r)
            swap(l, r);
        int j = LG[r - l + 1];
        return max(sp[l][j], sp[r - (1 << j) + 1][j]);
    }
    vll minimum_costs(vi H, vi L, vi R)
    {
        n = H.size();
        for(int i = 0  ; i < n; i ++)
            A[i] = H[i];
        q = L.size();
        LG[1] = 0 ;
        for(int i= 2; i < nax;i ++)
            LG[i] = LG[i/2] + 1;
        build();
        ll pref[n][n + 1];
        //cout << 5 << endl;
        for(int i = 0; i < n;i ++)
        {
            pref[i][0] = 0ll;
            //cout << i << '\n';
            for(int j = 0 ; j < n ;j++)
            {
                //cout << pref[i][j] << ' ';
                pref[i][j + 1] = pref[i][j] + rmq(i, j);
            }
            //cout << '\n';
        }
        vll ans(q, INF);
        for(int query = 0; query < q; query ++)
        {
            int l = L[query];
            int r = R[query];
            for(int i = l; i <= r; i ++)
            {
                ans[query] = min(ans[query], pref[i][r + 1] - pref[i][l]);
            }
        }
        return ans;
    }
    /*
    int32_t main()
    {
        int n, q;
        cin >> n >> q;
        vi H(n), L(q), R(q);
        for(int i = 0 ; i < n;i ++)
            cin >> H[i];
        for(int i = 0; i < q; i ++)
            cin >> L[i] >> R[i];
        vll C = minimum_costs(H, L, R);
        for(auto e: C)
            cout << e << '\n';
    }


/*
4 2
2 4 3 5
0 1
2 3
*/

Compilation message

meetings.cpp:94:1: warning: "/*" within comment [-Wcomment]
   94 | /*
      |

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 58 ms 71636 KB Output is correct
3 Correct 64 ms 71696 KB Output is correct
4 Correct 64 ms 71608 KB Output is correct
5 Correct 57 ms 71692 KB Output is correct
6 Correct 62 ms 71624 KB Output is correct
7 Correct 62 ms 71704 KB Output is correct
8 Correct 58 ms 71656 KB Output is correct
9 Correct 61 ms 71764 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 58 ms 71636 KB Output is correct
3 Correct 64 ms 71696 KB Output is correct
4 Correct 64 ms 71608 KB Output is correct
5 Correct 57 ms 71692 KB Output is correct
6 Correct 62 ms 71624 KB Output is correct
7 Correct 62 ms 71704 KB Output is correct
8 Correct 58 ms 71656 KB Output is correct
9 Correct 61 ms 71764 KB Output is correct
10 Correct 346 ms 197520 KB Output is correct
11 Correct 447 ms 197452 KB Output is correct
12 Correct 296 ms 197452 KB Output is correct
13 Correct 420 ms 197444 KB Output is correct
14 Correct 286 ms 197544 KB Output is correct
15 Correct 315 ms 197492 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2987 ms 506028 KB Output is correct
3 Runtime error 359 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2987 ms 506028 KB Output is correct
3 Runtime error 359 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 58 ms 71636 KB Output is correct
3 Correct 64 ms 71696 KB Output is correct
4 Correct 64 ms 71608 KB Output is correct
5 Correct 57 ms 71692 KB Output is correct
6 Correct 62 ms 71624 KB Output is correct
7 Correct 62 ms 71704 KB Output is correct
8 Correct 58 ms 71656 KB Output is correct
9 Correct 61 ms 71764 KB Output is correct
10 Correct 346 ms 197520 KB Output is correct
11 Correct 447 ms 197452 KB Output is correct
12 Correct 296 ms 197452 KB Output is correct
13 Correct 420 ms 197444 KB Output is correct
14 Correct 286 ms 197544 KB Output is correct
15 Correct 315 ms 197492 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2987 ms 506028 KB Output is correct
18 Runtime error 359 ms 786432 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -