Submission #837136

#	Time	Username	Problem	Language	Result	Execution time	Memory
837136		aaronkim00	Holiday (IOI14_holiday)	C++17	7 / 100	136 ms	65536 KiB

holiday

#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
const ll MOD = 998244353;

struct NODE{
    int cnt, l, r;
    ll sum;
};

int N, start, D, days;
vector<ll> arr;
vector<ll> A;
int nodeN;

NODE seg1[2000010];
int seg2[1200010];
int roots[100010];
ll decomp[100010];

void init2(int x, int s, int e){
    if(s==e){
        seg2[x] = 1;
    }
    else{
        seg2[x] = 0;
        int m = (s+e)/2;
        init2(x*2, s, m);
        init2(x*2+1, m+1, e);
    }
}

void propagate2(int x){
    if(seg2[x]){
        seg2[x*2] = seg2[x];
        seg2[x*2+1] = seg2[x];
        seg2[x] = 0;
    }
}

int query2(int x, int s, int e, int f){
    if(s==e){
        return seg2[x];
    }
    propagate2(x);
    int m = (s+e)/2;
    if(f<=m){
        return query2(x*2, s, m, f);
    }
    else{
        return query2(x*2+1, m+1, e, f);
    }
}

void update2(int x, int s, int e, int fs, int fe, int v){
    if(fe<s||e<fs){
        return;
    }
    if(fs<=s&&e<=fe){
        seg2[x] = v;
        return;
    }
    propagate2(x);
    int m = (s+e)/2;
    update2(x*2, s, m, fs, fe, v);
    update2(x*2+1, m+1, e, fs, fe, v);
}

void init1(int x, int s, int e){
    seg1[x].cnt = seg1[x].sum = 0;
    nodeN = max(nodeN, x);
    if(s!=e){
        seg1[x].l = x*2;
        seg1[x].r = x*2+1;
        int m = (s+e)/2;
        init1(x*2, s, m);
        init1(x*2+1, m+1, e);
    }
}

ll query1(int x, int s, int e, int a, int b){
    //printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
    if(a==1&&b==seg1[x].cnt){
        return seg1[x].sum;
    }
    if(s==e){
        printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
        printf("hello\n");
    }
    int m = (s+e)/2;
    ll result = 0;
    if(seg1[seg1[x].l].cnt >= a){
        result += query1(seg1[x].l, s, m, a, min(b, seg1[seg1[x].l].cnt));
    }
    if(seg1[seg1[x].l].cnt < b){
        result += query1(seg1[x].r, m+1, e, max(1, a-seg1[seg1[x].l].cnt), b-seg1[seg1[x].l].cnt);
    }
    return result;
}

void update1(int x, int s, int e, int f, ll v){
    //printf("--------- %d %d %d %d %lld\n", x, s, e, f, v);
    seg1[x].cnt++;
    seg1[x].sum += v;
    if(s!=e){
        int m = (s+e)/2;
        if(f<=m){
            seg1[++nodeN] = seg1[seg1[x].l];
            seg1[x].l = nodeN;
            update1(nodeN, s, m, f, v);
        }
        else{
            seg1[++nodeN] = seg1[seg1[x].r];
            seg1[x].r = nodeN;
            update1(nodeN, m+1, e, f, v);
        }
    }
}

vector<ll> oneWay(){
    int M = A.size()-1;
    if(M==0){
        vector<ll> result(D+1);
        return result;
    }
    nodeN = 0;
    init1(1, 1, N);
    init2(1, 1, D);

    roots[0] = 1;
    for(int i=1; i<=M; i++){
        roots[i] = ++nodeN;
        seg1[roots[i]] = seg1[roots[i-1]];
        update1(roots[i], 1, N, A[i], decomp[A[i]]);
    }

    for(int i=2; i<=M; i++){
        int left = i, right = D, mid = (left+right)/2;
        while(left<right){
            int t = query2(1, 1, D, mid);
            if((2*i-1<=mid || query1(roots[t], 1, N, max(2*t-mid, 1), 2*t-mid+1) < decomp[A[i]])){
                right = mid;
            }
            else{
                left = mid+1;
            }
            mid = (left+right)/2;
        }
        update2(1, 1, D, mid, D, i);
    }
    vector<ll> result;
    result.push_back(0);
    for(int i=1; i<=D; i++){
        int t = query2(1, 1, D, i);
        result.push_back(query1(roots[t], 1, N, max(2*t-i, 1), t));
    }
    return result;
}

vector<ll> roundTrip(){
    int M = A.size()-1;
    if(M==0){
        vector<ll> result(D+1);
        return result;
    }
    nodeN = 0;
    init1(1, 1, N);
    init2(1, 1, D);

    roots[0] = 1;
    for(int i=1; i<=M; i++){
        roots[i] = ++nodeN;
        seg1[roots[i]] = seg1[roots[i-1]];
        update1(roots[i], 1, N, A[i], decomp[A[i]]);
    }

    for(int i=2; i<=M; i++){
        int left = 2*i-1, right = D, mid = (left+right)/2;
        while(left<right){
            int t = query2(1, 1, D, mid);
            if((3*i-2<=mid || query1(roots[t], 1, N, max(3*t-mid-1, 1), 3*t-mid+1) < decomp[A[i]])){
                right = mid;
            }
            else{
                left = mid+1;
            }
            mid = (left+right)/2;
        }
        update2(1, 1, D, mid, D, i);
    }
    vector<ll> result;
    result.push_back(0);
    result.push_back(0);
    result.push_back(0);
    for(int i=1; i<=D; i++){
        int t = query2(1, 1, D, i);
        result.push_back(query1(roots[t], 1, N, max(3*t-i-1, 1), t));
    }
    return result;
}

vector<pair<ll, int> > temp;

ll findMaxAttraction(int input1, int input2, int input3, int input4[]){
    N = input1;
    start = input2;
    days = input3;
    for(int i=0; i<N; i++){
        arr.push_back(input4[i]);
        temp.push_back({input4[i], i});
    }
    D = 3*N;
    sort(all(temp));
    for(int i=0; i<N; i++){
        arr[temp[i].second] = i+1;
        decomp[i+1] = temp[i].first;
    }
    vector<ll> r1, r2, r3, r4;
    A.push_back(0);
    for(int i=start; i>=0; i--){
        A.push_back(arr[i]);
    }
    r1 = oneWay();
    A.clear();
    A.push_back(0);
    for(int i=start-1; i>=0; i--){
        A.push_back(arr[i]);
    }
    r2 = roundTrip();
    A.clear();
    A.push_back(0);
    for(int i=start+1; i<N; i++){
        A.push_back(arr[i]);
    }
    r3 = roundTrip();
    A.clear();
    A.push_back(0);
    for(int i=start; i<N; i++){
        A.push_back(arr[i]);
    }
    r4 = oneWay();
    ll result = 0;
    for(int i=0; i<=days; i++){
        result = max(result, r1[i]+r3[days-i]);
        result = max(result, r2[i]+r4[days-i]);
    }
    return result;
}

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