Submission #95333

#	Time	Username	Problem	Language	Result	Execution time	Memory
95333		Alexa2001	Holiday (IOI14_holiday)	C++17	24 / 100	189 ms	66560 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
#define mid ((st+dr)>>1)


using namespace std;
typedef long long ll;

const int Nmax = 1e5 + 5, lim = 1e9;

int D, N, S[Nmax];

#pragma pack(1)
struct Node
{
    Node *left, *right;
    int W; ll S;

    Node()
    {
        W = 0; S = 0;
        left = right = NULL;
    }

    Node(int _W, ll _S)
    {
        W = _W; S = _S;
        left = right = NULL;
    }

    Node(Node *_left, Node *_right)
    {
        left = _left, right = _right;
        W = (left? left->W : 0) + (right ? right->W : 0);
        S = (left? left->S : 0) + (right ? right->S : 0);
    }

    Node* update(int st, int dr, int pos)
    {
        if(st == dr)
            return new Node(W + 1, S + st);

        if(pos <= mid)
        {
            if(!left) left = new Node();
            return new Node( left->update(st, mid, pos), right );
        }
        else
        {
            if(!right) right = new Node();
            return new Node( left, right->update(mid+1, dr, pos) );
        }
    }

    ll query(int st, int dr, int nr)
    {
        if(!nr) return 0;

        if(st == dr)
            return min(S, (ll) nr * st);

        if(right && nr <= right -> W) return right->query(mid+1, dr, nr);
            else
            {
                if(right) return right->S + left->query(st, mid, nr - right->W);
                    else return left->query(st, mid, nr);
            }
    }
};

vector<Node*> aint;


void prepare_segTree(vector<int> &val)
{
    aint[0] = new Node();
    int i;
    for(i=1; i<val.size(); ++i)
    {
        aint[i] = aint[i-1];
        aint[i] = aint[i] -> update(1, lim, val[i]);
    }
}

ll Eval(int id, int nr)
{
    assert(nr >= 0);
    if(nr > aint[id] -> W) return aint[id] -> S;
    return aint[id] -> query(1, lim, nr);
}

int intersect(int x, int y, int T)
{
    int st, dr;
    st = T * y; dr = (T+1) * N;

    while(st <= dr)
        if(Eval(x, mid - T * x) > Eval(y, mid - T * y)) st = mid+1;
            else dr = mid-1;
    return st;
}

void Solve(vector<int> &val, vector<ll> &Ans1, vector<ll> &Ans2)
{
    aint.resize(val.size());
    prepare_segTree(val);

    Ans1.resize(D+1); Ans2.resize(D+1);
    N = val.size();

    int i, nr, j;

    /// Batch pt T = 1
    S[nr = 1] = 0;
    for(i=1; i<val.size(); ++i)
    {
        while(nr >= 2 && intersect(S[nr], i, 1) <= intersect(S[nr-1], S[nr], 1)) --nr;
        S[++nr] = i;
    }

    j = 0;
    for(i=0; i<=D; ++i)
    {
        while(j<nr && intersect(S[j], S[j+1], 1) <= i) ++j;
        Ans1[i] = Eval(S[j], i - S[j]);
    }

    /// Batch pt T = 2
    S[nr = 1] = 0;
    for(i=1; i<val.size(); ++i)
    {
        while(nr >= 2 && intersect(S[nr], i, 2) <= intersect(S[nr-1], S[nr], 2)) --nr;
        S[++nr] = i;
    }

    j = 0;
    for(i=0; i<=D; ++i)
    {
        while(j<nr && intersect(S[j], S[j+1], 2) <= i) ++j;
        Ans2[i] = Eval(S[j], i - 2*S[j]);
    }
}

ll findMaxAttraction(int n, int start, int d, int attraction[])
{
    int i; D = d;

    vector<int> A, B;
    vector<ll> T1, T2, T3, T4;

    A.push_back(0);
    B.push_back(0);

    for(i=start-1; i>=0; --i) A.push_back(attraction[i]);
    for(i=start+1; i<n; ++i)  B.push_back(attraction[i]);

    Solve(A, T1, T3);
    Solve(B, T4, T2);

    ll ans = 0;
    for(i=0; i <= d; ++i)
    {
        ans = max(ans, T1[i] + T2[d - i]);
        if(i < d) ans = max(ans, T1[i] + T2[d - i - 1] + attraction[start]);

        ans = max(ans, T3[i] + T4[d - i]);
        if(i < d) ans = max(ans, T3[i] + T4[d - i - 1] + attraction[start]);
    }

    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void prepare_segTree(std::vector<int>&)':
holiday.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<val.size(); ++i)
              ~^~~~~~~~~~~
holiday.cpp: In function 'void Solve(std::vector<int>&, std::vector<long long int>&, std::vector<long long int>&)':
holiday.cpp:115:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<val.size(); ++i)
              ~^~~~~~~~~~~
holiday.cpp:130:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<val.size(); ++i)
              ~^~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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