Submission #792218

#	Time	Username	Problem	Language	Result	Execution time	Memory
792218		caganyanmaz	Holiday (IOI14_holiday)	C++17	30 / 100	5062 ms	65536 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
#define pb push_back
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << (x) << "\n"
#else
#define debug(x)
#endif

struct SegTree
{
        int n;
        vector<int> left, right;
        vector<long long int> data;
        SegTree(int n) : n(n), left(1, -1), right(1, -1), data(1, 0) {}
        void expand(int index)
        {
                if (left[index] != -1)
                        return;
                left[index] = data.size();
                left.pb(-1), right.pb(-1), data.pb(0);
                right[index] = data.size();
                left.pb(-1), right.pb(-1), data.pb(0);
        }
        void change(int l, int r, int index, int i, int val)
        {
                if (i >= r || l > i)
                        return;
                if (l + 1 == r)
                {
                        data[index] += val;
                        return;
                }
                expand(index);
                int m = l+r>>1;
                change(l, m, left[index], i, val);
                change(m, r, right[index], i, val);
                data[index] = data[left[index]] + data[right[index]];
        }
        void change(int i, int val) { change(0, n, 0, i, val); }
        long long int get(int l, int r, int index, int ss, int ee)
        {
                if (ss >= r || l >= ee || index == -1)
                        return 0;
                if (ee >= r && l >= ss)
                        return data[index];
                int m = l+r>>1;
                long long int lres = get(l, m, left[index], ss, ee);
                long long int rres = get(m, r, right[index], ss, ee);
                return lres + rres;
        }
        long long int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};

int *v;
int n;
int start;
int d;



constexpr static int MXSIZE1 = 1e9 + 1;

long long int subtask1()
{
        SegTree st1(MXSIZE1);
        SegTree st2(MXSIZE1);
        long long int best = 0;
        for (int l = start; l >= 0; l--)
        {
                for (int r = start; r < n; r++)
                {
                        st1.change(v[r], 1);
                        st2.change(v[r], v[r]);
                        int remaining = d - (r - l) - min(start - l, r - start);
                        int ll = -1, rr = MXSIZE1;
                        while (rr - ll > 1)
                        {
                                int m = ll+rr>>1;
                                if (st1.get(m, MXSIZE1) < remaining)
                                        rr = m;
                                else
                                        ll = m;
                        }
                        if (l == 0 && r == 3)
                                debug(rr);
                        long long int sum = st2.get(rr, MXSIZE1);
                        if (rr != 0)
                        {
                                long long int leftover = remaining - st1.get(rr, MXSIZE1);
                                sum += leftover * (rr - 1);
                        }
                        debug(sum);
                        best = max(best, sum);
                }
                for (int r = start; r < n; r++)
                {
                        st1.change(v[r], -1);
                        st2.change(v[r], -v[r]);
                }
                if (l > 0)
                {
                        st1.change(v[l-1], 1);
                        st2.change(v[l-1], v[l-1]);
                }
        }
        return best;
}


constexpr static int MXSIZE = 101;
long long int subtask2()
{
        SegTree st1(MXSIZE);
        SegTree st2(MXSIZE);
        long long int best = 0;
        for (int i = 0; i < n && i < d; i++)
        {
                st1.change(v[i], 1);
                st2.change(v[i], v[i]);
                int l = -1, r = MXSIZE;
                while (r - l > 1)
                {
                        int m = l+r>>1;
                        if (st1.get(m, MXSIZE) + i < d)
                                r = m;
                        else
                                l = m;
                }
                long long int sum = st2.get(r, MXSIZE);
                if (r != 0)
                {
                        long long int remaining = d - st1.get(r, MXSIZE) - i;
                        sum += remaining * (r-1);
                }
                best = max(best, sum);
        }
        return best;
}

long long int findMaxAttraction(int nn, int sstart, int dd, int aattraction[]) {
        n = nn;
        start = sstart;
        d = dd;
        v = aattraction;
        int mx = 0;
        for (int i = 0; i < n; i++)
                mx = max(mx, v[i]);
        if (mx <= 100)
                return subtask2();
        return subtask1();

}

Compilation message (stderr)

holiday.cpp: In member function 'void SegTree::change(int, int, int, int, int)':
holiday.cpp:37:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |                 int m = l+r>>1;
      |                         ~^~
holiday.cpp: In member function 'long long int SegTree::get(int, int, int, int, int)':
holiday.cpp:49:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |                 int m = l+r>>1;
      |                         ~^~
holiday.cpp: In function 'long long int subtask1()':
holiday.cpp:81:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |                                 int m = ll+rr>>1;
      |                                         ~~^~~
holiday.cpp: In function 'long long int subtask2()':
holiday.cpp:126:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |                         int m = l+r>>1;
      |                                 ~^~

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