Submission #229384

#	Time	Username	Problem	Language	Result	Execution time	Memory
229384		osaaateiasavtnl	휴가 (IOI14_holiday)	C++14	7 / 100	91 ms	65540 KiB

holiday

#include<bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair                                                                                                       
#define f first
#define s second                                                                       
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
int start, d, a[N];
vector <int> c;

struct Node {
    int cnt;
    ll sum;
    Node *l, *r;
    Node () {
        cnt = sum = 0;
        l = r = NULL;
    }   
};
Node *t[N];  

Node *build(int l, int r) {
    Node *t = new Node();
    if (l == r)
        return t;
    int m = (l + r) >> 1;
    t->l = build(l, m);
    t->r = build(m + 1, r);
    return t;
}   
Node *add(Node *t, int l, int r, int i) {
    Node *ans = new Node();
    if (l == r) {
        ans->cnt = t->cnt + 1;
        ans->sum = t->sum + c[i];
        return ans;
    }   
    int m = (l + r) >> 1;
    if (i <= m) {
        ans->l = add(t->l, l, m, i);
        ans->r = t->r;
    }   
    else {
        ans->l = t->l;
        ans->r = add(t->r, m + 1, r, i);
    }   
    ans->cnt = ans->l->cnt + ans->r->cnt;
    ans->sum = ans->l->sum + ans->r->sum;
    return ans;
}   
ll sum(Node *tl, Node *tr, int l, int r, int k) {
    if (l == r)
        return k * c[l];
    int m = (l + r) >> 1;
    int r_cnt = tr->r->cnt - tl->r->cnt;
    if (k <= r_cnt)
        return sum(tl->r, tr->r, m + 1, r, k);
    else
        return (tr->r->sum - tl->r->sum) + sum(tl->l, tr->l, l, m, k - r_cnt);
}   

ll ans = 0;
ll get(int l, int r) {
    if (start < l || start > r) {
        cout << "LMAO" << endl;
        exit(1);
    }   
    int go = (start - l) + (r - start) + min(start - l, r - start);
    if (d <= go)
        return 0;
    int k = d - go;

    //cout << "sum " << l << ' ' << r << ' ' << min(r - l + 1, k) << endl;
    //cout << "res : " << sum(t[l], t[r + 1], 0, N, min(r - l + 1, k)) << endl;

    return sum(t[l], t[r + 1], 0, N, min(r - l + 1, k));
}   
int get_opt(int r, int opt_l, int opt_r) {
    ll nn = 0, opt = opt_l;
    for (int l = opt_l; l <= opt_r; ++l) {
        ll t = get(l, r);
        if (t > nn) {
            nn = t;
            opt = l;
        }   
    }   
    ans = max(ans, nn);
    return opt;
}   
void solve(int l, int r, int opt_l, int opt_r) {
    if (r < l)
        return;
    int m = (l + r) >> 1;
    int opt_m = get_opt(m, opt_l, opt_r);
    solve(l, m - 1, opt_l, opt_m);
    solve(m + 1, r, opt_m, opt_r);                        
}   
long long int findMaxAttraction(int n, int start_, int d_, int a_[]) {
    
    start = start_;
    d = d_;
    for (int i = 0; i < n; ++i)
        a[i] = a_[i];

    for (int i = 0; i < n; ++i) 
        c.app(a[i]);
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(all(c), a[i]) - c.begin();
    
    t[0] = build(0, N);
    for (int i = 0; i < n; ++i) 
        t[i + 1] = add(t[i], 0, N, a[i]);

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

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