Submission #31181

#	Time	Username	Problem	Language	Result	Execution time	Memory
31181		pasa3232	Holiday (IOI14_holiday)	C++14	100 / 100	1673 ms	11672 KiB

holiday

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

ll n, start, d, ans, data[100010], ch[100010];
struct C{
    ll num, inx;
    bool operator<(const C &r)const{
        return r.num<num;
    }
}A[100010];
struct B{
    ll cnt, sum;
    B operator+(const B &r){
        return (B){r.cnt+cnt, r.sum+sum};
    }
}tree[400010];

void update(ll node, ll s, ll e, ll pos, ll val){
    if(e<pos||s>pos) return;
    if(s==e){
        tree[node].cnt=val;
        if(val==1) tree[node].sum=A[s].num;
        else tree[node].sum=0;
        return;
    }
    ll m=s+e>>1;
    update(node*2, s, m, pos, val);
    update(node*2+1, m+1, e, pos, val);
    tree[node]=tree[node*2]+tree[node*2+1];
}

ll get(ll node, ll s, ll e, ll num){
    ll m=s+e>>1;
    if(tree[node].cnt==num) return tree[node].sum;
    if(s==e) return tree[node].sum;
    if(tree[node*2].cnt>=num) return get(node*2, s, m, num);
    if(tree[node*2].cnt<num) return tree[node*2].sum+get(node*2+1, m+1, e, num-tree[node*2].cnt);
}

/// tree를 e+1부터 q까지 체워 놓고 들어감
void dnc(ll s, ll e, ll p, ll q){
    if(s>e) return;
//    printf("%lld %lld %lld %lld\n", s, e, p, q);
    ll mid=s+e>>1, v, M=-1;

    for(ll i=mid; i<=e; i++) update(1, 0, n-1, ch[i], 1);

    for(ll i=q; i>=p; i--){
        ll len=i-start+i-mid, s=-1;
        if(d-len>0) s=get(1, 0, n-1, d-len);
        if(d-len==0) s=0;
//        printf("(%lld %lld %lld)\n", i, d-len, s);
        if(s>M) M=s, v=i;
        update(1, 0, n-1, ch[i], 0);
    }
    if(M==-1) v=p;
    ans=max(ans, M);

    ///p~v (+)
    for(ll i=p; i<=v; i++) update(1, 0, n-1, ch[i], 1);
    dnc(s, mid-1, p, v);
    ///mid~e(-)  v+1~q (+)
    for(ll i=mid; i<=e; i++) update(1, 0, n-1, ch[i], 0);
    for(ll i=v+1; i<=q; i++) update(1, 0, n-1, ch[i], 1);
    dnc(mid+1, e, v, q);
}

ll findMaxAttraction(int N, int Start, int D, int attraction[]){
//    freopen("input.txt", "r", stdin);
    n=N, start=Start, d=D;
    for(ll i=0; i<n; i++) data[i]=attraction[i], A[i].num=data[i], A[i].inx=i;
    if(d) ans=data[start];
    sort(A, A+n);
    for(ll i=0; i<n; i++) ch[A[i].inx]=i;
    for(ll i=start; i<n; i++) update(1, 0, n-1, ch[i], 1);
    dnc(0, start-1, start, n-1);
    for(ll i=0; i<n; i++) update(1, 0, n-1, ch[i], 0);

    for(ll i=0; i<n/2; i++) swap(data[i], data[n-i-1]);
    for(ll i=0; i<n; i++) ch[n-A[i].inx-1]=i;
    start=n-start-1;

    for(ll i=start; i<n; i++) update(1, 0, n-1, ch[i], 1);

    dnc(0, start-1, start, n-1);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void update(ll, ll, ll, ll, ll)':
holiday.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     ll m=s+e>>1;
           ^
holiday.cpp: In function 'll get(ll, ll, ll, ll)':
holiday.cpp:35:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     ll m=s+e>>1;
           ^
holiday.cpp: In function 'void dnc(ll, ll, ll, ll)':
holiday.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     ll mid=s+e>>1, v, M=-1;
             ^
holiday.cpp: In function 'll get(ll, ll, ll, ll)':
holiday.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
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