Submission #794266

#	Time	Username	Problem	Language	Result	Execution time	Memory
794266		Ronin13	Holiday (IOI14_holiday)	C++17	100 / 100	1843 ms	36912 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

using namespace std;

const int nmax = 400001;

struct node{
    ll ones, sum;
    node(){
        ones = sum = 0;
    }
}t[4 * nmax];

void update(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos)
    return;
    if(l == r){
        if(val == 0) t[v].sum = t[v].ones = 0;
        else t[v].sum = val, t[v].ones = 1;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v+ 1, m + 1, r, pos, val);
    t[v].ones = t[2 * v].ones + t[2 * v + 1].ones;
    t[v].sum = t[2 * v].sum + t[2 * v + 1].sum;
}

ll getfirst(int v, int l, int r, int val, ll sum = 0){
    if(l == r){
        return sum;
    }
    int m = (l + r) / 2;
    if(t[2 * v].ones <= val){
        return 
            getfirst(2 * v + 1, m + 1,r, val - t[2 * v].ones, sum + t[2 * v].sum);
    }
    return getfirst(2 * v, l, m, val, sum);
}

int s;
int d;
int n;
ll ans[nmax][4];
ll pos[nmax], val[nmax];
void divi1(int l, int r, int optl, int optr, int ind){
    if(l > r)
        return;
    int m = (l + r) / 2;
    ll cur = 0, opti;
    cur = -1e18;
    for(int i = optr; i >= optl; i--){
        ll x = s - i;
        x *= ind / 2 + 1;
        update(1, 0, n, pos[i], val[i]);
        if(m < x)  continue;
        if(cur < getfirst(1, 0, n, m - x)){
            cur = getfirst(1, 0, n, m - x);
            opti = i;
        }
    }
    for(int i = optr; i >= optl; i--)
        update(1, 0, n, pos[i], 0);
    ans[m][ind] = cur;
    divi1(l, m - 1, opti, optr, ind);
    for(int i = optr; i > opti; --i)
        update(1, 0, n, pos[i], val[i]);
    divi1(m + 1, r, optl, opti, ind);
    for(int i = optr; i > opti; --i)
        update(1, 0, n, pos[i], 0);
}
//win wasvla dabrunebis gareshe
void divi2(int l, int r, int optl, int optr, int ind){
    if(l > r)
        return;
    int m = (l + r) / 2;
    ll cur = -1e18, opti;
    for(int i = optl; i <= optr; i++){
        int x = i - s;
        x *= (ind / 2 + 1);
       // cout << x << ' ';
        update(1, 0, n, pos[i], val[i]);
        if(m < x) continue;
        ll y = getfirst(1, 0, n, m - x);
        if(y > cur)
            cur = y, opti = i;
    }
    for(int i = optl; i <= optr; i++)
        update(1, 0, n, pos[i], 0);
    ans[m][ind] = cur;
    divi2(l, m - 1, optl, opti, ind);
    for(int i = optl; i < opti; i++){
        update(1, 0, n ,pos[i], val[i]);
    }
    divi2(m + 1, r, opti, optr, ind);
    for(int i = optl; i < opti; i++)
        update(1, 0, n, pos[i], 0);
}


long long int findMaxAttraction(int N, int start, int d, int a[]) {
    n = N;
    pii b[n + 1];
    s = start;
    for(int i= 0; i < n; i++){
        val[i] = a[i];
        b[i] = {a[i], i};
        if(i == s) b[i].f = 0;
    }
    sort(b, b + n);
    reverse(b, b + n);
    for(int i = 0; i < n; ++i)
        pos[b[i].s] = i;
    val[s] = 0;
    
    divi2(0, d, s, n - 1, 3);
    divi1(0, d, 0, s, 0);
    divi1(0, d, 0, s, 2);
    divi2(0, d, s, n - 1, 1);
    //cout << t[1].sum;
    
    
    
    ll res = 0;
    for(int i = 0; i <= d; i++){
        res = max(res, ans[i][3] + ans[d - i][0]);
        res = max(res, ans[i][2] + ans[d - i][1]);
        if(i < d){
            ll x = max(x, ans[i][3]+ ans[d - i - 1][0]);
            x = max(ans[i][2] + ans[d - i - 1][1], x);
            res = max(res, x + a[s]);
        }
    }
    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void divi1(int, int, int, int, int)':
holiday.cpp:59:17: warning: 'opti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     ll cur = 0, opti;
      |                 ^~~~
holiday.cpp: In function 'void divi2(int, int, int, int, int)':
holiday.cpp:86:21: warning: 'opti' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     ll cur = -1e18, opti;
      |                     ^~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:138:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |             ll x = max(x, ans[i][3]+ ans[d - i - 1][0]);
      |                ^

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