Submission #421083

#	Time	Username	Problem	Language	Result	Execution time	Memory
421083		xt0r3	Holiday (IOI14_holiday)	C++14	93 / 100	675 ms	12392 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;

constexpr int N = 1 << 18;
long long t[N], dp[N];
bool bent[N];
int cut[N], n, d, cl, cr, id[N];
bool volt[N];
vector<long long> v;

struct FenwickTree{
    int sz;//ez 2-hatvany
    vector<long long> t;

    FenwickTree(){}
    FenwickTree(int _sz): sz(_sz){
        t.assign(sz + 1, 0);//1-tol sz-ig
    }

    void add(int pos, long long val){
        for(int i = pos; i <= sz; i += i & -i) t[i] += val;
    }

    long long get(int pos){
        long long ret = 0;
        for(int i = pos; i > 0; i -= i & -i) ret += t[i];
        return ret;
    }

    int src(int l, int r, long long sum){
        if(l == r) return l;
        int m = (l + r) / 2;
        if(t[m] >= sum){//nagy
            return src(l, m, sum);
        }
        else{
            return src(m + 1, r, sum - t[m]);
        }
    }

    int src(long long sum){
        return src(1, sz, sum);
    }
};


FenwickTree cnt, sum;

int index(long long x){
    return v.end() - lower_bound(v.begin(), v.end(), x);//1-tol indexelt a fenwick
}

long long val(int pos){
    if(pos > v.size()) return 0;
    return v[v.size() - pos];//pos az epp a v.end-tol visszafele van
}

void left(){
    cnt.add(id[cl], -1);
    sum.add(id[cl], -val(id[cl]));
    cl++;
}

void right(){
    cnt.add(id[cr], 1);
    sum.add(id[cr], val(id[cr]));
    cr++;
}

long long solve(int _N, int start, int D, int attraction[]) {
    n = _N; d = D;
    cnt = FenwickTree(N);
    sum = FenwickTree(N);

    //coordinate compression
    v.resize(n);
    for(int i = 0; i < n; i++) v[i] = attraction[i];
    sort(v.begin(), v.end());
    v.resize((int)(unique(v.begin(), v.end()) - v.begin()));

    //cuts of endpoints
    cut[start] = 1; //start 0-tol indexelve epp a start - 1 nalunk [start + 1, n] dp[i]: elmegyek a startbol i-be, aztan vissza cut[i]-ig
    cut[n + 1] = n + 1;
    volt[start] = volt[n + 1] = 1;

    for(int i = 1; i <= n; i++){
        id[i] = index(attraction[i - 1]);//id-k precompja
    }

    deque<pair<int, int> > uj = {{start, n + 1}}, regi;

    while(!uj.empty()){
        regi = uj;
        uj.clear();
        cl = 1;
        cr = 1;
        cnt = FenwickTree(N);
        sum = FenwickTree(N);

        while(!regi.empty()){//aktualis indexet megcsinaljuk
            int l = regi.front().first, r = regi.front().second;
            regi.pop_front();
            int m = (l + r) / 2;

            //cout << m << ' ' << l << ' ' << r << ' ' << cut[l] << ' ' << cut[r] << endl;
            //system("PAUSE");

            while(cr <= m){//beletesszuk
                right();
            }
            //cout << "ITT" << endl;
            while(cl < min(start + 1, cut[l])){//kivesszuk start ->
                left();
            }
            //cout << "ITT" << endl;

            for(int i = cut[l]; i <= min(m, cut[r]); i++){
                long long rem = d - (2 * m - start - 1 - i);//ennyi marad a lepeseken tul - a start 0tol van indexelve
                if(rem >= 0){
                    long long hol = cnt.src(rem);
                    long long levon = max(0ll, cnt.get(hol) - rem);//ennyiszer szerepel pluszban a faban egy ertek
                    long long most = sum.get(hol) - levon * val(hol);
                    if(dp[m] <= most){
                        dp[m] = most;
                        cut[m] = i;
                    }
                }
                if(i < min({start + 1, m, cut[r]})) left();//cut[r]-bol nem kell kilepni
            }
            if(cut[m] == 0) cut[m] = m;
            //cout << m << ' ' << cut[m] << endl;

            int nw = (l + m) / 2;
            if(!volt[nw]){
                volt[nw] = 1;
                uj.push_back(make_pair(l, m));
            }
            nw = (m + r) / 2;
            if(!volt[nw]){
                volt[nw] = 1;
                uj.push_back(make_pair(m, r));
            }
        }

    }

    return *max_element(dp, dp + n + 1);
}

long long findMaxAttraction(int _N, int start, int D, int attraction[]) {
    long long ans1 = solve(_N, start, D, attraction);
    reverse(attraction, attraction + _N);
    start = _N - start - 1;
    fill(volt, volt + _N, 0);
    fill(cut, cut + _N, 0);
    fill(dp, dp + _N, 0);
    long long ans2 = solve(_N, start, D, attraction);
    return max(ans1, ans2);
}

Compilation message (stderr)

holiday.cpp: In function 'long long int val(int)':
holiday.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(pos > v.size()) return 0;
      |        ~~~~^~~~~~~~~~

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