Submission #852710

#	Time	Username	Problem	Language	Result	Execution time	Memory
852710		tvgk	Holiday (IOI14_holiday)	C++17	7 / 100	36 ms	9052 KiB

holiday

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define task ""
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
 
ii tree[mxN * 4], a[mxN];
ll num, mx, tmp, ans, vt[mxN];
int j;
 
void Up(int j)
{
    tree[j].se = tree[j * 2].se + tree[j * 2 + 1].se;
 
    tree[j].fi = 0;
    if (tree[j * 2].se)
        tree[j].fi += tree[j * 2].fi;
    if (tree[j * 2 + 1].se)
        tree[j].fi += tree[j * 2 + 1].fi;
}
 
void Build(int j, int l, int r)
{
    if (l == r)
    {
        tree[j].fi = a[l].fi;
        return;
    }
 
    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
}
 
ll Get(int j, int l, int r)
{
  	if ((!tree[j].se) || (num <= 0))
        return 0;
  
    if (tree[j].se <= num)
    {
        num -= tree[j].se;
        return tree[j].fi;
    }
 
    int mid = (l + r) / 2;
    return Get(j * 2 + 1, mid + 1, r) + Get(j * 2, l, mid);
}
 
void Update(int j, int l, int r, int vt, int tt)
{
    if (l > vt || vt > r)
        return;
 
    if (l == r)
    {
        tree[j].se = tt;
        return;
    }
 
    int mid = (l + r) / 2;
    Update(j * 2, l, mid, vt, tt);
    Update(j * 2 + 1, mid + 1, r, vt, tt);
 
    Up(j);
}
 
long long int findMaxAttraction(int n, int stt, int day, int att[])
{
    stt++;
    for (int i = 1; i <= n; i++)
    {
        a[i].fi = att[i - 1];
        a[i].se = i;
    }
 
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        vt[a[i].se] = i;
 
    Build(1, 1, n);
    for (int i = stt; i <= n; i++)
        Update(1, 1, n, vt[i], 1);
 
    j = n;
    for (int i = stt; i >= 1; i--)
    {
        Update(1, 1, n, vt[i], 1);
        num = day - (j - i) - min(stt - i, j - stt);
        mx = Get(1, 1, n);
 
        while (j > stt)
        {
            Update(1, 1, n, vt[j], 0);
            j--;
 
            num = day - (j - i) - min(stt - i, j - stt);
            tmp = Get(1, 1, n);
 
            if (tmp >= mx)
                mx = tmp;
            else
            {
                j++;
                Update(1, 1, n, vt[j], 1);
                break;
            }
        }
 
        ans = max(ans, mx);
    }
 
    return ans;
}

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