oj.uz

Submission #71457

# Submission time Handle Problem Language Result Execution time Memory
71457 2018-08-24T18:14:15 Z yusufake Holiday (IOI14_holiday) C++
100 / 100
 522 ms 42096 KB 
#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

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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 37216 KB Output is correct
2 Correct 98 ms 37508 KB Output is correct
3 Correct 82 ms 37740 KB Output is correct
4 Correct 93 ms 37892 KB Output is correct
5 Correct 93 ms 37892 KB Output is correct
6 Correct 25 ms 37892 KB Output is correct
7 Correct 46 ms 37892 KB Output is correct
8 Correct 56 ms 37892 KB Output is correct
9 Correct 17 ms 37892 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 39764 KB Output is correct
2 Correct 98 ms 40036 KB Output is correct
3 Correct 142 ms 40036 KB Output is correct
4 Correct 7 ms 40036 KB Output is correct
5 Correct 3 ms 40036 KB Output is correct
6 Correct 5 ms 40036 KB Output is correct
7 Correct 5 ms 40036 KB Output is correct
8 Correct 381 ms 41280 KB Output is correct
9 Correct 522 ms 42096 KB Output is correct