Submission #589207

#	Time	Username	Problem	Language	Result	Execution time	Memory
589207		FatihSolak	Holiday (IOI14_holiday)	C++17	23 / 100	5010 ms	3720 KiB

holiday

#include <bits/stdc++.h>
#define N 100005
#include"holiday.h"
using namespace std;
struct BIT{
    vector<long long> bit;
    int n;
    BIT(int size){
        n = size;
        bit.assign(n,0);
    }
    void upd(int pos,int val){
        for(;pos < n;pos += pos & -pos){
            bit[pos] += val;
        }
    }
    long long get(int pos){
        long long ret = 0;
        for(;pos > 0;pos -= pos & -pos){
            ret += bit[pos];
        }
        return ret;
    }
    int get_kth(int k){
        int ret = 0;
        for(int i = 20;i>=0;i--){
            if((1<<i) + ret < n && bit[ret + (1<<i)] < k){
                k -= bit[ret + (1<<i)];
                ret += (1<<i);
            }
        }
        return ret+1;
    }
};
int rel[N];
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans = 0;
    vector<int> compress;
    for(int i = 0;i<n;i++){
        compress.push_back(-attraction[i]);
    }
    sort(compress.begin(),compress.end());
    compress.resize(unique(compress.begin(),compress.end())-compress.begin());
    for(int i = 0;i<compress.size();i++){
        rel[i+1] = -compress[i];
    }
    for(int i = 0;i<n;i++){
        attraction[i] = lower_bound(compress.begin(),compress.end(),-attraction[i])-compress.begin() + 1;
    }
    for(int l = 0;l<=start;l++){
        BIT bt1(n);
        BIT bt2(n);
        for(int j = l;j<start;j++){
            bt1.upd(attraction[j],1);
            bt2.upd(attraction[j],rel[attraction[j]]);
        }
        for(int r = start;r<n;r++){
            bt1.upd(attraction[r],1);
            bt2.upd(attraction[r],rel[attraction[r]]);
            int cost = 0;
            if(l == start || r == start)cost = abs(l-start)+abs(r-start);
            else cost = abs(l-r)+min(abs(l-start),abs(r-start));
            int left = d - cost;
            if(left <= 0)continue;
            int pos = bt1.get_kth(left) -1;
            ans = max(ans,bt2.get(pos) + (left -  bt1.get(pos)) * (rel[pos+1]));
        }
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0;i<compress.size();i++){
      |                   ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53