oj.uz

답안 #229391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229391 2020-05-04T11:22:54 Z osaaateiasavtnl 휴가 (IOI14_holiday) C++14
100 / 100
 283 ms 49776 KB 
#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, hol, a[N];
vector <int> c;

struct Node {
    int cnt;
    ll sum;
    int l, r;
};
int ptr = 0;
const int V = N * 20;
Node d[V];  
int t[N];

int newNode() {
    ++ptr;
    return ptr - 1;
}   

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

ll ans = 0;
ll get(int l, int r) {
    int go = (start - l) + (r - start) + min(start - l, r - start);
    if (hol <= go)
        return 0;
    int k = hol - go;
    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 hol_, int a_[]) {
    for (int i = 0; i < V; ++i) {
        d[i].cnt = d[i].sum = 0;
        d[i].l = d[i].r = -1;
    }   

    start = start_;
    hol = hol_;
    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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 47232 KB Output is correct
2 Correct 31 ms 47352 KB Output is correct
3 Correct 30 ms 47352 KB Output is correct
4 Correct 30 ms 47352 KB Output is correct
5 Correct 30 ms 47224 KB Output is correct
6 Correct 30 ms 47360 KB Output is correct
7 Correct 35 ms 47360 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 49136 KB Output is correct
2 Correct 77 ms 49136 KB Output is correct
3 Correct 83 ms 49312 KB Output is correct
4 Correct 78 ms 49136 KB Output is correct
5 Correct 84 ms 49136 KB Output is correct
6 Correct 48 ms 47868 KB Output is correct
7 Correct 60 ms 48372 KB Output is correct
8 Correct 67 ms 48628 KB Output is correct
9 Correct 41 ms 47864 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 31 ms 47352 KB Output is correct
3 Correct 33 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 34 ms 47360 KB Output is correct
6 Correct 30 ms 47224 KB Output is correct
7 Correct 30 ms 47480 KB Output is correct
8 Correct 31 ms 47352 KB Output is correct
9 Correct 31 ms 47360 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 49136 KB Output is correct
2 Correct 91 ms 49776 KB Output is correct
3 Correct 98 ms 48500 KB Output is correct
4 Correct 43 ms 47404 KB Output is correct
5 Correct 31 ms 47352 KB Output is correct
6 Correct 32 ms 47360 KB Output is correct
7 Correct 31 ms 47360 KB Output is correct
8 Correct 283 ms 49768 KB Output is correct
9 Correct 273 ms 49776 KB Output is correct