Submission #71457

#	Time	Username	Problem	Language	Result	Execution time	Memory
71457		yusufake	Holiday (IOI14_holiday)	C++98	100 / 100	522 ms	42096 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
#include"holiday.h"

#define tm (tl+tr >> 1)
#define mp make_pair
#define pp pair < ll , int >
#define st first
#define nd second
#define ll long long
const int N = 1e5 + 5;
int ss[N*20],L[N*20],R[N*20],root[N],nw,T[N],n,k,orta;
ll s[N*20],ans;

int up(int v, int tl, int tr, int i){
    if(tl > i || tr < i) return v;
    int w = ++nw;
    if(tl < tr){
        L[w] = up(L[v],tl,tm,i);
        R[w] = up(R[v],tm+1,tr,i);
    }
    ss[w] = ss[v]+1;
    s[w] = s[v]+T[i];
    return w;
}

ll bs(int a, int b, int tl, int tr, int k){
    if(tl == tr) return 1LL * T[tl] * min(k , ss[a]-ss[b]);
    if(k > ss[ R[a] ] - ss[ R[b] ])
        return bs(L[a],L[b],tl,tm,k-(ss[ R[a] ] - ss[ R[b] ])) + s[ R[a] ] - s[ R[b] ];
    return bs(R[a],R[b],tm+1,tr,k);
}

void f(int l, int r, int opl, int opr){
    if(l > r) return;
    int i, m = l+r >> 1;
    pp mx = mp(0,0);
    for(i=opl;i<=opr;i++){
        mx = max(mx , mp(bs(root[m],root[i-1],1,n+1,k-(min(orta-i,m-orta)+m-i)),i));
    }
    i = mx.nd;
    //if(m == 86) cout << orta << " " << k-(min(orta-i,m-orta)+m-i) << " aa\n"; 
    //cout << m << " " << mx.st << " " << mx.nd << " " << opl << " " << opr << " zzz\n";
    ans = max(ans , mx.st);
    f(l,m-1,opl,mx.nd);
    f(m+1,r,mx.nd,opr);
}
ll findMaxAttraction(int zz, int s, int d, int *A){
    n = zz;
    orta = s+1;
    k = d;
    int i,j,p=0;
    for(i=0;i<n;i++) T[i+1] = A[i];
    sort(T+1,T+n+1);
    for(i=0;i<n;i++){
        j = lower_bound(T+1 , T+n+1 , A[i]) - T;
        root[i+1] = p = up(p,1,n+1,j);
    }
    f(orta,n,1,orta);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'int up(int, int, int, int)':
holiday.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
holiday.cpp:19:27: note: in expansion of macro 'tm'
         L[w] = up(L[v],tl,tm,i);
                           ^~
holiday.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
holiday.cpp:20:24: note: in expansion of macro 'tm'
         R[w] = up(R[v],tm+1,tr,i);
                        ^~
holiday.cpp: In function 'long long int bs(int, int, int, int, int)':
holiday.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
holiday.cpp:30:32: note: in expansion of macro 'tm'
         return bs(L[a],L[b],tl,tm,k-(ss[ R[a] ] - ss[ R[b] ])) + s[ R[a] ] - s[ R[b] ];
                                ^~
holiday.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
holiday.cpp:31:25: note: in expansion of macro 'tm'
     return bs(R[a],R[b],tm+1,tr,k);
                         ^~
holiday.cpp: In function 'void f(int, int, int, int)':
holiday.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int i, m = l+r >> 1;
                ~^~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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