oj.uz

Submission #825053

# Submission time Handle Problem Language Result Execution time Memory
825053 2023-08-14T14:03:51 Z Wael Holiday (IOI14_holiday) C++14
100 / 100
 2735 ms 23640 KB 
#include<bits/stdc++.h>
#include "holiday.h"
//#include "grader.cpp"
using namespace std;
#define F first
#define S second
typedef long long ll;
int const M = 1e5 + 10 , N = 30e5 + 10;
int s[M] , cnt[N] , Left[N] , Right[N] , cur = 1 , L , R , k , Index;
ll Size = (1 << 30) , ans , sum[N] , dp[M];

void Add(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) { 
    if(i == 0) return;
    if(lx == rx) {
        sum[node] += lx;
        ++cnt[node];
        return;
    } 
    int mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Add(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Add(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}

void Remove(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) {
    if(i == 0) return;
    if(lx == rx) {
        sum[node] -= lx;
        --cnt[node];
        return;
    } 
    ll mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Remove(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Remove(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}

ll Get(ll need , ll node = 1 , ll lx = 1 , ll rx = Size) { //cout << need << " " << lx << endl;
    if(node == 0) return 0;
    if(need <= 0) return 0;
    if(lx == rx) return min(need , (ll)cnt[node]) * lx;
    ll mid = (lx + rx) / 2;
    if(cnt[Right[node]] >= need) {
        //cout << lx << " " << rx << " " << cnt[Right[node]] << endl;
        return Get(need , Right[node] , mid + 1 , rx);
    }
    else {
        need -= cnt[Right[node]];
        return sum[Right[node]] + Get(need , Left[node] , lx , mid);
    }
}

void Move(int l , int r) {
    if(l > r) swap(l , r);

    while(L < l) {
        Remove(s[L]);
        ++L;
    }

    while(L > l) {
        --L;
        Add(s[L]);
    }

    while(R < r) {
        ++R;
        Add(s[R]);
    }

    while(R > r) {
        Remove(s[R]);
        --R;
    }
}

void Divide(int l , int r , int i , int j) { 
    //cout << "in = " <<  l << " " << r << " " << i << " " << j << endl;
    if(i > j) return;
    int mid = (i + j) / 2;

    ll mx = 0 , Optimal = j;
    for(int I = l ; I <= r ; ++I) {
        Move(mid , I);
        //cout << sum[1] << endl;
        int d = k;
        d -= abs(mid - Index);
        d -= abs(mid - I);
        //cout << "d = " << d << endl;
        ll res = Get(d);
        if(res > mx) {
            mx = res;
            dp[mid] = res;
            Optimal = I;
        }
    }

    ans = max ( ans , mx );

    //cout << "mid = " << mid << " " << dp[mid] << endl;
    Divide(l , Optimal , i , mid - 1);
    Divide(Optimal , r , mid + 1 , j);
}

long long int findMaxAttraction(int n, int start, int D , int attraction[]) {
    ++start;
    k = D; Index = start;
    for(int i = 1 ; i <= n ; ++i) s[i] = attraction[i - 1];

    int d = D;
    for(int i = start ; i <= n ; ++i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = start ; i <= n ; ++i) Remove(s[i]);

    d = D;
    for(int i = start ; i >= 1 ; --i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = 1 ; i <= start ; ++i) Remove(s[i]);

    if(start > 1 && start < n) Divide(1 , start , start , n);
    if(start > 1 && start < n) Divide(start , n , 1 , start );

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1296 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 38 ms 1236 KB Output is correct
4 Correct 13 ms 1236 KB Output is correct
5 Correct 38 ms 1236 KB Output is correct
6 Correct 12 ms 852 KB Output is correct
7 Correct 22 ms 980 KB Output is correct
8 Correct 26 ms 1132 KB Output is correct
9 Correct 10 ms 884 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1868 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 34 ms 1852 KB Output is correct
5 Correct 30 ms 1756 KB Output is correct
6 Correct 10 ms 1108 KB Output is correct
7 Correct 10 ms 784 KB Output is correct
8 Correct 9 ms 704 KB Output is correct
9 Correct 8 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1876 KB Output is correct
2 Correct 77 ms 23640 KB Output is correct
3 Correct 1526 ms 12124 KB Output is correct
4 Correct 41 ms 1644 KB Output is correct
5 Correct 10 ms 724 KB Output is correct
6 Correct 9 ms 724 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 2735 ms 10428 KB Output is correct
9 Correct 2714 ms 10276 KB Output is correct