Submission #589330

#	Time	Username	Problem	Language	Result	Execution time	Memory
589330		FatihSolak	Holiday (IOI14_holiday)	C++17	100 / 100	211 ms	7612 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;
    }
    vector<pair<pair<int,int>,pair<int,int>>> q;
    q.push_back({{0,start},{start,n-1}});
    while(q.size()){
        vector<pair<pair<int,int>,pair<int,int>>> nw;
        BIT bt1(n);
        BIT bt2(n);
        int l = 0,r = -1;
        for(auto u:q){
            //cout << u.first.first << " " << u.first.second << endl;
            //cout << u.second.first << " " << u.second.second << endl;
            if(u.first.first > u.first.second)continue;
            int m = (u.first.first + u.first.second)/2;
            while(l < m){
                bt1.upd(attraction[l],-1);
                bt2.upd(attraction[l],-rel[attraction[l]]);
                l++;
            }
            int opt = u.second.first;
            long long maxi = 0;
            for(int i = u.second.first;i<=u.second.second;i++){
                while(r < i){
                    r++;
                    bt1.upd(attraction[r],1);
                    bt2.upd(attraction[r],rel[attraction[r]]);
                }
                //cout << l << " " << m << " " << r << " " << i << endl;
                int cost = 0;
                if(m == start || i == start)cost = abs(m-start)+abs(i-start);
                else cost = abs(m-i)+min(abs(m-start),abs(i-start));
                int left = min(i-m+1,d - cost);
                if(left <= 0)continue;
                int pos = bt1.get_kth(left) -1;
                long long nowans = bt2.get(pos) + (left -  bt1.get(pos)) * (rel[pos+1]);
                //cout << cost << " " << left << " " << nowans << endl;
                if(nowans > maxi){
                    maxi = nowans;
                    opt = i;
                }
                ans = max(ans,nowans);
            }
            //cout << opt << endl;
            nw.push_back({{u.first.first,m-1},{u.second.first,opt}});
            nw.push_back({{m+1,u.first.second},{opt,u.second.second}});
        }
        q = nw;
    }
    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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53