oj.uz

답안 #249517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249517 2020-07-15T07:52:01 Z Mercenary 휴가 (IOI14_holiday) C++14
100 / 100
 1488 ms 7548 KB 
#include "holiday.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n , a[maxn];

ll s[maxn * 4];
int cnt[maxn * 4];
ll res = 0;
int order[maxn] , d , id[maxn];
int st = 0;

void flip(int x , int l , int r , int pos){
    if(l == r){
//        cout << pos << " " << a[id[l]] << endl;
        if(cnt[x] == 0)cnt[x] = 1 , s[x] = a[order[l]];
        else cnt[x] = 0 , s[x] = 0;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid)flip(x * 2 , l , mid , pos);
    else flip(x * 2 + 1 , mid + 1 , r , pos);
    s[x] = s[x * 2] + s[x * 2 + 1];
    cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}
ll get(int x , int l , int r , int k){
    if(cnt[x] <= k)return s[x];
    if(l == r || k <= 0)return 0;
    ll sum = 0;
    int mid = l + r >> 1;
    sum += get(x * 2 + 1 , mid + 1 , r , min(k , cnt[x * 2 + 1]));
    k -= min(k , cnt[x * 2 + 1]);
    sum += get(x * 2 , l , mid , k);
    return sum;
}
void flip(int pos){flip(1,1,n,pos);}
ll get(int k){return get(1,1,n,k);};

int L = 1 , R = 0;
void correct(int l , int r){
    while(L < l)flip(id[L++]);
    while(L > l)flip(id[--L]);
    while(R < r)flip(id[++R]);
    while(R > r)flip(id[R--]);
}

void solve(int l , int r , int optl , int optr){
    if(l > r)return;
    int mid = l + r >> 1;
    pair<ll,int> best = mp(-1,-1);
    for(int i = optl ; i <= mid && i <= optr ; ++i){
        correct(i , mid);
        best = max(best , mp(get(d - (mid - i) - (mid - st)) , i));
//        cout << i << " " << mid << " " << cnt[1] << " " << d - (mid - i) - (mid - st) << " " << get(d - (mid - i) - (mid - st)) << endl;
    }
    res = max(res,best.first);
    solve(l , mid - 1 , optl , best.second);
    solve(mid + 1 , r , best.second,optr);
}

void Try(){
    L = 1 , R = 0;
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    iota(order + 1 , order + n + 1 ,1);
    sort(order + 1 , order + n + 1 ,[&](const int x , const int y){return a[x] < a[y];});
//    for(int i = 1 ; i <= n ; ++i)cout << order[i] << " ";cout << endl;
    for(int i = 1 ; i <= n ; ++i)id[order[i]] = i;
    solve(st , n , 1 , n);
}

ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
    n = _n;
    st = start + 1;d = _d;
    for(int i = 1 ; i <= n ; ++i)a[i] = attraction[i - 1];
    Try();
    for(int i = 1 ; i <= n ; ++i)a[i] = attraction[n - i];
    st = n - start;
    Try();
    return res;
}

//static int N, start, D, A[100005];
//
//int main() {
//    scanf("%d%d%d", &N, &start, &D);
//    for ( int i = 0; i < N; i++ ) scanf("%d", &A[i]);
//    printf("%lld\n", findMaxAttraction(N, start, D, A));
//}

Compilation message

holiday.cpp: In function 'void flip(int, int, int, int)':
holiday.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'll get(int, int, int, int)':
holiday.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 541 ms 6904 KB Output is correct
2 Correct 315 ms 6784 KB Output is correct
3 Correct 502 ms 6904 KB Output is correct
4 Correct 554 ms 6904 KB Output is correct
5 Correct 756 ms 6792 KB Output is correct
6 Correct 167 ms 5692 KB Output is correct
7 Correct 372 ms 6016 KB Output is correct
8 Correct 506 ms 6264 KB Output is correct
9 Correct 113 ms 5376 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 5120 KB Output is correct
2 Correct 11 ms 5120 KB Output is correct
3 Correct 11 ms 5120 KB Output is correct
4 Correct 22 ms 5120 KB Output is correct
5 Correct 23 ms 5120 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 7544 KB Output is correct
2 Correct 539 ms 7448 KB Output is correct
3 Correct 445 ms 6264 KB Output is correct
4 Correct 20 ms 5120 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 1423 ms 7548 KB Output is correct
9 Correct 1488 ms 7452 KB Output is correct