Submission #1145516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145516		Matbubble	Holiday (IOI14_holiday)	C++20	24 / 100	5087 ms	3352 KiB

holiday

#include"holiday.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";

/*  
MC lover
*/

struct fentree{
    vector<long long>ft;
    int n;
    fentree (int n):n(n), ft(n+1){}
    long long querie(int posi){
        long long res=0;
        while(posi>0){
            res+=ft[posi];
            posi-=posi&-posi;
        }
        return res;
    }

    void add(int posi, long long val){
        while(posi<=n){
            ft[posi]+=val;
            posi+=posi&-posi;
        }
    }

    int bs(int k){
        int aux=querie(n);
        if(aux<=k) return 1;
        int res=0;
        int l=1, r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            if(aux-querie(mid-1)>=k){
                res=mid;
                l=mid+1;
            }else r=mid-1;
        }
        return res;
    }
};

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans=0;
    vector<long long> v(n);
    set<long long>cast;
    map<long long, int>val;
    map<int, long long>rev;
    for(int i=0 ; i<n ; i++){
        v[i]=attraction[i];
        cast.insert(v[i]);
    }
    int posi=1;
    for(long long x:cast){
        val[x]=posi;
        rev[posi]=x;
        posi++;
    }
    //left
    {
        fentree freq(n), pref(n);
        for(int i=start ; i<n ; i++){
            int left=d-(i-start);
            if(left<=0) break;
            pref.add(val[v[i]], v[i]);
            freq.add(val[v[i]], 1);
            int posi=freq.bs(left);
            int now=freq.querie(n)-freq.querie(posi-1);
            long long curr=pref.querie(n)-pref.querie(posi-1);
            if(now>left){
                now-=left;
                curr-=now*rev[posi];
            }
            // cout<<left<<" "<<curr<<"\n";
            ans=max(ans, curr);
        }
    }
    //right
    {
        fentree freq(n), pref(n);
        for(int i=start ; i>=0 ; i--){
            int left=d-(start-i);
            if(left<=0) break;
            pref.add(val[v[i]], v[i]);
            freq.add(val[v[i]], 1);
            int posi=freq.bs(left);
            int now=freq.querie(n)-freq.querie(posi-1);
            long long curr=pref.querie(n)-pref.querie(posi-1);
            if(now>left){
                now-=left;
                curr-=now*rev[posi];
            }
            // cout<<left<<" "<<curr<<"\n";
            ans=max(ans, curr);
        }
    }
    //both
    {
        //start right
        {
            for(int i=start ; i>=0 ; i--){
                fentree freq(n), pref(n);
                for(int j=i ; j<n ; j++){
                    pref.add(val[v[j]], v[j]);
                    freq.add(val[v[j]], 1);
                    if(j<=start) continue;
                    int left=d-(((2*(start-i))+(j-start)));
                    if(left<=0) break;
                    int posi=freq.bs(left);
                    int now=freq.querie(n)-freq.querie(posi-1);
                    long long curr=pref.querie(n)-pref.querie(posi-1);
                    if(now>left){
                        now-=left;
                        curr-=now*rev[posi];
                    }
                    // cout<<left<<" "<<curr<<"\n";
                    ans=max(ans, curr);
                }
            }
        }
        //start left
        {
            for(int i=start ; i<n ; i++){
                fentree freq(n), pref(n);
                for(int j=i ; j>=0 ; j--){
                    pref.add(val[v[j]], v[j]);
                    freq.add(val[v[j]], 1);
                    if(j>=start) continue;
                    int left=d-(((2*(i-start))+(start-j)));
                    if(left<=0) break;
                    int posi=freq.bs(left);
                    int now=freq.querie(n)-freq.querie(posi-1);
                    long long curr=pref.querie(n)-pref.querie(posi-1);
                    if(now>left){
                        now-=left;
                        curr-=now*rev[posi];
                    }
                    // cout<<left<<" "<<curr<<"\n";
                    ans=max(ans, curr);
                }
            }
        }
    }
    return ans;
}

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