Submission #293605

#	Time	Username	Problem	Language	Result	Execution time	Memory
293605		Trickster	Meetings (IOI18_meetings)	C++14	0 / 100	5551 ms	5076 KiB

meetings

#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
// #include "meetings.h"

using namespace std;

#define sq 320
#define maxN 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

ll n, q;
pii p[maxN];
ll A[maxN];
ll B[maxN];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    q = L.size();
    n = H.size();

    vector <ll> E;
    for(ll i = 0; i < n; i++) {
        p[i].ss = n;
        while(!E.empty() && H[E.back()] < H[i]) p[E.back()].ss = i, E.pop_back();

        p[i].ff = -1;
        if(!E.empty()) p[i].ff = E.back();

        E.pb(i);
    }
    // for(int i = 0; i < n; i++) cout << p[i].ff << " " << p[i].ss << "\n";

    vector <ll> ans;
    for(ll i = 0; i < q; i++) {
        ll mn = 2e9;
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));

        for(ll h = L[i]; h <= R[i]; h++) {
            if(h == L[i] || H[h] >= H[h-1]) A[h] = A[p[h].ff] + (h - max(p[h].ff + 1, L[i]) + 1) * H[h];
            else A[h] = A[h-1] + H[h];
        }
        for(ll h = R[i]; h >= L[i]; h--) {
            if(h == R[i] || H[h] >= H[h+1]) B[h] = B[p[h].ss] + (min(p[h].ss - 1, R[i]) - h + 1) * H[h];
            else B[h] = B[h+1] + H[h];

            mn = min(mn, A[h] + B[h] - H[h]);

            // cout << h << " - " << A[h] << " " << B[h] << " " << H[h] << "\n";
        }

        ans.pb(mn);
    }

    return ans;
}

// int main()
// {
//     cin >> n >> q;
//     ll x, y;
//     vector <int> a, b, c;
//     for(ll i = 1; i <= n; i++) cin >> x, a.pb(x);
//     for(ll i = 1; i <= q; i++) cin >> x >> y, b.pb(x), c.pb(y);

//     vector <ll> res = minimum_costs(a, b, c);

//     for(auto i: res) cout << i << " ";
// }
/*
4 2
2 4 3 5
0 2
1 3
*/

Compilation message (stderr)

meetings.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
meetings.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40