Submission #788960

#	Time	Username	Problem	Language	Result	Execution time	Memory
788960		aymanrs	Meetings (IOI18_meetings)	C++14	17 / 100	50 ms	13608 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
const int K = 18;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    int n = H.size(), q = L.size();
    int nx[n], pr[n];
    int p = -1;
    for(int i = 0;i < n;i++) {
        if(H[i] == 2) p = i;
        pr[i] = p;
    }
    p = n;
    int sp[n][K];
    for(int i = n-1;i >= 0;i--){
        if(H[i] == 2) p = i;
        nx[i] = p;
        sp[i][0] = max(nx[i]-pr[i]-1, 0);
    }
    for(int k = 1;k < K;k++){
        for(int i = 0;i + (1<<k) <= n;i++){
            sp[i][k] = max(sp[i][k-1], sp[i+(1<<k-1)][k-1]);
        }
    }
    vector<long long> Q;
    if(H[0] > 2){
        Q.push_back(4000000001LL);
        return Q;
    }
    for(int i = 0;i < q;i++){
        int l = L[i], r = R[i];
        if(nx[l] > r) {
            Q.push_back(r-l+1);
            continue;
        }
        if(nx[l] >= pr[r]){
            Q.push_back((r-l+1)*2 - max(max(nx[l]-l, r-pr[r]), 0));
            continue;
        }
        int ans = max(max(nx[l]-l, r-pr[r]), 0);
        l = nx[l];
        r = pr[r];
        int d = r-l+1;
        for(int j = 0;j < K;j++){
            if(d&(1<<j)){
                ans = max(ans, sp[l][j]);
                l += 1<<j;
            }
        }
        Q.push_back(2*(R[i]-L[i]+1)-ans);
    }
    return Q;
}

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:21:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |             sp[i][k] = max(sp[i][k-1], sp[i+(1<<k-1)][k-1]);
      |                                                 ~^~

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