Submission #781335

#	Time	Username	Problem	Language	Result	Execution time	Memory
781335		vjudge1	Meetings (IOI18_meetings)	C++17	0 / 100	22 ms	32132 KiB

meetings

#include "meetings.h"
#define I signed 
#include<bits/stdc++.h>
using namespace std;
long long rmq[100100][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();
    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(long long j = 1; j < 20; j++)
        for(long long i = 0; i <= arr.size()-(1<<j);i++)
            rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<j-1)][j-1]);
    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]) 
                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:29:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(long long i = 0; i <= arr.size()-(1<<j);i++)
      |                              ~~^~~~~~~~~~~~~~~~~~~~
meetings.cpp:30:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |             rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<j-1)][j-1]);
      |                                                    ~^~
meetings.cpp:32:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(long long i = 0; i < L.size(); i++) {
      |                          ~~^~~~~~~~~~

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