oj.uz

답안 #157481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157481 2019-10-11T23:11:53 Z jhnah917 휴가 (IOI14_holiday) C++14
100 / 100
 954 ms 41696 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> p;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, st, d;
p arr[101010]; //idx, cnt
ll ans = 0;

struct Seg{
    vector<p> tree[303030];
    int bias;

    void init(int n){
        for(bias=1; bias<=n; bias<<=1);
        for(int i=1; i<=n; i++){
            int x = bias | i;
            while(x){
                tree[x].push_back(arr[i]);
                x >>= 1;
            }
        }
        for(int i=bias-1; i>=1; i--){
            sort(all(tree[i]));
            for(int j=1; j<tree[i].size(); j++) tree[i][j].y += tree[i][j-1].y;
        }
    }

    p get(int node, int s, int e){
        p ret(0, 0);
        int l = lower_bound(tree[node].begin(), tree[node].end(), p(s, -1)) - tree[node].begin();
        int r = lower_bound(tree[node].begin(), tree[node].end(), p(e+1, -1)) - tree[node].begin();
        ret.x = r - l;
        if(r) ret.y = tree[node][r-1].y;
        if(l) ret.y-= tree[node][l-1].y;
        return ret;
    }

    ll query(int s, int e, int k){
        int x = 1; ll ret = 0; k++;
        while(x <= bias){
            auto tmp = get(x << 1, s, e);
            if(k <= tmp.x) x = (x << 1);
            else{
                x = (x << 1 | 1);
                k -= tmp.x;
                ret += tmp.y;
            }
        }
        return ret;
    }
}seg;

void dnc(int s, int e, int l, int r){
    if(s > e) return;
    int m = s + e >> 1;

    ll mx = -1, K = l;
    
    for(int i=l; i<=r; i++){
        int cnt = d - (i - m + min(i-st, st-m));
        if(cnt <= 0) continue;
        ll now = seg.query(m, i, min(cnt, i - m + 1));
        if(mx < now){
            mx = now; K = i;
        }
    }
    ans = max(ans, mx);
    dnc(s, m-1, l, K);
    dnc(m+1, e, K, r);
}

ll findMaxAttraction(int _n, int _st, int _d, int inp[]){
    n = _n; st = _st + 1; d = _d;
    for(int i=1; i<=n; i++) arr[i] = {i, inp[i-1]};
    sort(arr+1, arr+n+1, [&](p &a, p &b){
        return a.y > b.y;
    });
    seg.init(n);
    dnc(1, st, st, n);
    return ans;
}

Compilation message

holiday.cpp: In member function 'void Seg::init(int)':
holiday.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1; j<tree[i].size(); j++) tree[i][j].y += tree[i][j-1].y;
                          ~^~~~~~~~~~~~~~~
holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7496 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 40760 KB Output is correct
2 Correct 174 ms 40916 KB Output is correct
3 Correct 178 ms 40896 KB Output is correct
4 Correct 174 ms 40876 KB Output is correct
5 Correct 216 ms 38080 KB Output is correct
6 Correct 61 ms 16108 KB Output is correct
7 Correct 113 ms 23780 KB Output is correct
8 Correct 143 ms 27248 KB Output is correct
9 Correct 44 ms 13552 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8184 KB Output is correct
2 Correct 12 ms 8312 KB Output is correct
3 Correct 12 ms 8440 KB Output is correct
4 Correct 20 ms 8312 KB Output is correct
5 Correct 16 ms 8184 KB Output is correct
6 Correct 11 ms 7672 KB Output is correct
7 Correct 11 ms 7608 KB Output is correct
8 Correct 11 ms 7672 KB Output is correct
9 Correct 11 ms 7664 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 40844 KB Output is correct
2 Correct 154 ms 41684 KB Output is correct
3 Correct 196 ms 22196 KB Output is correct
4 Correct 18 ms 8312 KB Output is correct
5 Correct 11 ms 7672 KB Output is correct
6 Correct 11 ms 7672 KB Output is correct
7 Correct 11 ms 7672 KB Output is correct
8 Correct 887 ms 41684 KB Output is correct
9 Correct 954 ms 41696 KB Output is correct