Submission #781355

#	Time	Username	Problem	Language	Result	Execution time	Memory
781355		vjudge1	Meetings (IOI18_meetings)	C++17	36 / 100	362 ms	196300 KiB

meetings

#include "meetings.h"
#define I signed 
#include<bits/stdc++.h>
using namespace std;
long long rmq[1000100][20];
long long query(long long l, long long r) {
    if(l>r) return 0;
    long long x = 31-__builtin_clz(r-l);
    return max(rmq[l][x], rmq[r-(1<<x)+1][x]);
}
vector<long long> minimum_costs(vector<I> H, vector<I> L, vector<I> R) {
    long long n = H.size();
    if(n<5001) {
        long long C[n][n];
        memset(C, 0, sizeof C);
        for(int i = 0; i < n; i++) {
            int mx = 0;
            long long ans = 0;
            for(int j = i; j < n; j++)
                C[i][j] = ans += mx = max(mx, H[j]);
            ans = 0;
            mx = 0;
            for(int j = i+1; j--;)
                C[i][j] = ans += mx = max(mx, H[j]);
        }
        vector<long long> ans(L.size(), 1e18);
        for(int i = 0; i < L.size(); i++)
            for(int j = L[i]; j <= R[i]; j++)
                ans[i] = min(ans[i], C[j][L[i]]+C[j][R[i]]-H[j]);
        return ans;
    }
    vector<pair<long long, long long>> arr;
    long long from[n];
    long long l = -1;
    for(long long i = 0; i < n; i++) {
        if(H[i]-2) {
            if(l==-1)
                l=i;
        } else {
            if(l!=-1)
                rmq[arr.size()][0] = i-l, arr.push_back({l, i-1});
            l=-1;
        }
        from[i] = arr.size()-(l<0);
    }
    if(l>=0) arr.push_back({l, n-1});
    for(int j = 1; j < 16; j++) {
        int i = 0;
        while(rmq[i+(1<<j-1)][j-1])
            rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<j-1)][j-1]), i++;
    }
    vector<long long> ans;
    for(long long i = 0; i < L.size(); i++) {
        long long a = from[L[i]], b = from[R[i]];
        if(b<0) {
            ans.push_back((R[i]-L[i]+1)*2);
            continue;
        }
        long long a2 = 0;
        if(a>=0)
            if(arr[a].second >= L[i]) {
                if(arr[a].second>=R[i]) {
                    ans.push_back(R[i]-L[i]+1);
                    continue;
                }
                a2 = arr[a].second - L[i] + 1;
            }
        a++;
        if(arr[b].second >= R[i])
            a2 = max(a2, R[i] - arr[b].first + 1), b--;
        a2 = max(a2, query(a, b));
        ans.push_back((R[i]-L[i]+1)*2-a2);
    }
    return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i = 0; i < L.size(); i++)
      |                        ~~^~~~~~~~~~
meetings.cpp:49:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |         while(rmq[i+(1<<j-1)][j-1])
      |                         ~^~
meetings.cpp:50:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |             rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<j-1)][j-1]), i++;
      |                                                    ~^~
meetings.cpp:53:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(long long i = 0; i < L.size(); i++) {
      |                          ~~^~~~~~~~~~

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