oj.uz

Submission #657767

# Submission time Handle Problem Language Result Execution time Memory
657767 2022-11-11T01:42:25 Z lkh3happy Holiday (IOI14_holiday) C++14
100 / 100
 756 ms 9440 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

long long A[100001], t[400001], cnt[400001], ll=1, rr=0;
vector<long long> cp;

void upd(int l, int r, int n, int x, int v){
    if(r<x || x<l) return;
    if(l==r){
        cnt[n]+=v; t[n]+=v*cp[l-1]; return;
    }
    int m=l+r>>1;
    upd(l, m, n*2, x, v); upd(m+1, r, n*2+1, x, v);
    t[n]=t[n*2]+t[n*2+1]; cnt[n]=cnt[n*2]+cnt[n*2+1];
}

long long kth(int l, int r, int n, int k){
    if(l==r) return min(cnt[n], 1LL*k)*cp[l-1];
    int m=l+r>>1;
    if(cnt[n*2+1]>=k) return kth(m+1, r, n*2+1, k);
    return kth(l, m, n*2, k-cnt[n*2+1])+t[n*2+1];
}

void move(int l, int r){
    for(;rr<r;) upd(1, cp.size(), 1, A[++rr], 1);
    for(;ll>l;) upd(1, cp.size(), 1, A[--ll], 1);
    for(;rr>r;) upd(1, cp.size(), 1, A[rr--], -1);
    for(;ll<l;) upd(1, cp.size(), 1, A[ll++], -1);
}

long long dnc(int l, int r, int s, int e, int st, int d){
    if(r<l) return 0;
    int m=l+r>>1;
    long long mx=0, idx=e;
    if(d-(m-st+m-e)>0){
        move(e, m);
        mx=kth(1, cp.size(), 1, d-(m-st+m-e));
        for(int i=e-1;i>=s && d-(m-st+m-i);i--){
            move(i, m);
            if(mx<kth(1, cp.size(), 1, d-(m-st+m-i))) mx=kth(1, cp.size(), 1, d-(m-st+m-i)), idx=i;
        }
    }
    return max(mx, max(dnc(l, m-1, s, idx, st, d), dnc(m+1, r, idx, e, st, d)));
}

long long solve(int n, int s, int d){
    for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
    return dnc(s, n, 1, s, s, d);
}

long long findMaxAttraction(int n, int s, int d, int At[]){
    for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for(int i=1;i<=n;i++) A[i]=lower_bound(cp.begin(), cp.end(), A[i])-cp.begin()+1;
    long long ans=solve(n, s, d);
    reverse(A+1, A+n+1); s=n+1-s;
    return max(ans, solve(n, s, d));
    return 0;
}

Compilation message

holiday.cpp: In function 'void upd(int, int, int, int, int)':
holiday.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int kth(int, int, int, int)':
holiday.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int dnc(int, int, int, int, int, int)':
holiday.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=l+r>>1;
      |           ~^~
holiday.cpp: In function 'long long int solve(int, int, int)':
holiday.cpp:49:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |     for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
      |     ^~~
holiday.cpp:49:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |     for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
      |                                               ^~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:54:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |     for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
      |     ^~~
holiday.cpp:54:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |     for(int i=0;i<n;i++) A[i+1]=At[i], cp.push_back(At[i]); s++;
      |                                                             ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6868 KB Output is correct
2 Correct 3 ms 6868 KB Output is correct
3 Correct 3 ms 6824 KB Output is correct
4 Correct 3 ms 6868 KB Output is correct
5 Correct 4 ms 6832 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct
7 Correct 5 ms 6868 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8520 KB Output is correct
2 Correct 22 ms 8776 KB Output is correct
3 Correct 26 ms 8776 KB Output is correct
4 Correct 28 ms 8776 KB Output is correct
5 Correct 76 ms 8692 KB Output is correct
6 Correct 29 ms 7504 KB Output is correct
7 Correct 48 ms 8012 KB Output is correct
8 Correct 52 ms 8144 KB Output is correct
9 Correct 22 ms 7352 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6996 KB Output is correct
2 Correct 4 ms 6996 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 13 ms 7016 KB Output is correct
5 Correct 13 ms 6968 KB Output is correct
6 Correct 5 ms 6976 KB Output is correct
7 Correct 6 ms 6868 KB Output is correct
8 Correct 5 ms 6868 KB Output is correct
9 Correct 5 ms 6868 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8648 KB Output is correct
2 Correct 171 ms 8524 KB Output is correct
3 Correct 131 ms 8108 KB Output is correct
4 Correct 11 ms 6996 KB Output is correct
5 Correct 5 ms 6868 KB Output is correct
6 Correct 6 ms 6868 KB Output is correct
7 Correct 5 ms 6868 KB Output is correct
8 Correct 756 ms 9408 KB Output is correct
9 Correct 731 ms 9440 KB Output is correct