oj.uz

Submission #756673

# Submission time Handle Problem Language Result Execution time Memory
756673 2023-06-12T04:26:29 Z ByeWorld Holiday (IOI14_holiday) C++14
100 / 100
 2645 ms 36760 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
typedef pair<ll,ll> pii;

int val[MAXN];
struct node {
    int l, r, mid; ll sum, cnt; 
    node *le, *ri;
    void bd(int l2, int r2){
        l = l2; r = r2; mid = (l+r)/2;
        sum = 0; cnt = 0;
        if(l==r) return;
        le = new node(); le->bd(l, mid);
        ri = new node(); ri->bd(mid+1, r);
    }
    ll que(int w){
        if(w<=0) return 0;
        if(cnt <= w) return sum;
        if(l == r) return 1ll*val[l]*w;
        if(ri->cnt >= w) return ri->que(w);
        return le->que(w - ri->cnt) + ri->que(ri->cnt);
    }
    pii upd(int x, int p){
        if(r<x || x<l) return {sum, cnt};
        if(l==r && l==x){
            sum += 1ll*val[x]*p; cnt += p;
            return {sum, cnt};
        }
        pii lupd = le->upd(x, p); pii rupd = ri->upd(x, p);
        sum = lupd.fi + rupd.fi; cnt = lupd.se + rupd.se;
        return {sum, cnt}; 
    }
} A;

int n, sta, d;
int a[MAXN];
map<int,int> idx;
ll ret = 0;
int le = 1, ri = 0;

void setlr(int l,int r){
    while(le < l){
        A.upd(idx[a[le++]], -1);
    } //mid-1, out
    while(le > l){
        A.upd(idx[a[--le]], 1);
    } //mid, in
    while(ri < r){
        A.upd(idx[a[++ri]], 1);
    } //optl, in
    while(ri > r){
        A.upd(idx[a[ri--]], -1);
    } //optr+1, out
}

void solve(int l, int r, int optl, int optr){
    if(l > r) return;
    int mid = (l+r)/2, opt;
    ll dp = -INF; //cari value mid
    // mid - le udh ke build
    if(ri-optl <= optr-ri){
        for(int i=optl; i<=optr; i++){
            setlr(mid,i);
            // mid - i
            // d-(sta-mid)-(i-mid)
            ll can = A.que(d-sta + 2*mid - i);
            //cout << mid << ' ' << i << ' ' << can << "que\n";
            if(dp < can){
                dp = can;
                opt = i;
            }
        }
        solve(mid+1, r, opt, optr); solve(l, mid-1, optl, opt); 
    } else {
        for(int i=optr; i>=optl; i--){
            setlr(mid,i);
            ll can = A.que(d-sta + 2*mid - i);
            //cout << mid << ' ' << i << ' ' << can << "que\n";
            if(dp <= can){
                dp = can;
                opt = i;
            }
        }
        solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr); 
    }
    //cout << mid << ' '<< opt << ' ' << dp << "dp\n";
    ret = max(ret, dp);
}

long long int findMaxAttraction(int N, int start, int D, int X[]) {
	n = N; sta = start; d = D;
    sta++;
    set <int> s;
	for(int i=0; i<=n-1; i++){
        a[i+1] = X[i];
        s.insert(a[i+1]);
    }
    int index = 0;
    for(auto in : s){
        idx[in] = ++index;
        val[index] = in;
        //cout << in << ' ' << index << "ind\n";
    }
    
    //cout << "\nA\n";
    le = sta; ri = sta-1;
    A.bd(1, MAXN);
    solve(1, sta, sta, n);

	for(int i=1; i<n-i+1; i++) swap(a[i], a[n-i+1]);
	sta = n-sta+1;
    //cout << "\nB\n";
    le = sta; ri = sta-1;
	A.bd(1, MAXN);
    solve(1, sta, sta, n);

	return ret;
}

Compilation message

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:90:42: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr);
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25744 KB Output is correct
2 Correct 19 ms 25684 KB Output is correct
3 Correct 20 ms 25668 KB Output is correct
4 Correct 20 ms 25684 KB Output is correct
5 Correct 28 ms 25632 KB Output is correct
6 Correct 21 ms 25680 KB Output is correct
7 Correct 20 ms 25692 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 26324 KB Output is correct
2 Correct 147 ms 26200 KB Output is correct
3 Correct 137 ms 26444 KB Output is correct
4 Correct 118 ms 26216 KB Output is correct
5 Correct 161 ms 26364 KB Output is correct
6 Correct 64 ms 25936 KB Output is correct
7 Correct 96 ms 26088 KB Output is correct
8 Correct 111 ms 26160 KB Output is correct
9 Correct 46 ms 25876 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26064 KB Output is correct
2 Correct 22 ms 25680 KB Output is correct
3 Correct 26 ms 25964 KB Output is correct
4 Correct 35 ms 25932 KB Output is correct
5 Correct 33 ms 25932 KB Output is correct
6 Correct 23 ms 25856 KB Output is correct
7 Correct 24 ms 25788 KB Output is correct
8 Correct 26 ms 25676 KB Output is correct
9 Correct 23 ms 25684 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 26892 KB Output is correct
2 Correct 272 ms 36760 KB Output is correct
3 Correct 732 ms 30588 KB Output is correct
4 Correct 43 ms 25956 KB Output is correct
5 Correct 25 ms 25676 KB Output is correct
6 Correct 25 ms 25676 KB Output is correct
7 Correct 29 ms 25672 KB Output is correct
8 Correct 2582 ms 35688 KB Output is correct
9 Correct 2645 ms 35560 KB Output is correct