oj.uz

Submission #1009602

# Submission time Handle Problem Language Result Execution time Memory
1009602 2024-06-27T16:50:13 Z hotboy2703 Holiday (IOI14_holiday) C++14
100 / 100
 1058 ms 8664 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN=1e5+100;
ll a[MAXN];
vector <ll> b;
ll n,s,d;
pll tree[MAXN*4];
void update(ll id,ll l,ll r,ll i,pll v){
    if (l > i || r < i)return;
    if (l==r){
        tree[id].fi+=v.fi,tree[id].se+=v.se;
        return;
    }
    ll mid = (l + r) >> 1;
    update(id<<1,l,mid,i,v);
    update(id<<1|1,mid+1,r,i,v);
    tree[id].fi=tree[id<<1].fi+tree[id<<1|1].fi;
    tree[id].se=tree[id<<1].se+tree[id<<1|1].se;
}
ll get_kth(ll id,ll l,ll r,ll k){
//    cout<<id<<' '<<l<<' '<<r<<' '<<k<<endl;
    if (l==r){
//        cout<<"WOW "<<tree[id].fi<<' '<<tree[id].se<<' '<<k<<endl;
        if (k >= tree[id].fi)return tree[id].se;
        else return tree[id].se/tree[id].fi*k;
    }
    ll mid = (l + r) >> 1;
    if (tree[id<<1|1].fi >= k)return get_kth(id<<1|1,mid+1,r,k);
    else return get_kth(id<<1,l,mid,k-tree[id<<1|1].fi)+tree[id<<1|1].se;
}
void ins(ll i){
    update(1,0,n-1,a[i],MP(1,b[a[i]]));
}
void del(ll i){
    update(1,0,n-1,a[i],MP(-1,-b[a[i]]));
}
ll res = 0;
ll cur_l,cur_r;
ll query(ll l,ll r,ll k){
//    cout<<"QUERY "<<l<<' '<<r<<' '<<k<<'\n';
    while (cur_l > l)ins(--cur_l);
    while (cur_r < r)ins(++cur_r);
    while (cur_l < l)del(cur_l++);
    while (cur_r > r)del(cur_r--);
//    cout<<"SUS"<<endl;
    ll res = get_kth(1,0,n-1,k);
//    cout<<"WHAT"<<endl;
    return res;
}
void dnc(ll l,ll r,ll optl,ll optr){

    if (l > r)return;
//    cout<<l<<' '<<r<<' '<<optl<<' '<<optr<<'\n';
    ll mid = (l + r) >> 1;
    ll optmid,best;
    optmid = -1,best = -1;
    for (ll x = optl;x <= optr;x ++){
//        cout<<"ST "<<x<<endl;
        ll rem = d-(s+x-2*mid);
        if (rem < 0)continue;
        ll tmp = query(mid,x,rem);
//        cout<<"END "<<x<<endl;
        if (tmp > best){
            tie(best,optmid) = tie(tmp,x);
        }

    }
    res = max(res,best);
    dnc(l,mid-1,optl,optmid);
    dnc(mid+1,r,optmid,optr);
}
void solve(){
    memset(tree,0,sizeof tree);
    cur_l = 1;
    cur_r = 0;
    dnc(0,s,s+1,n-1);
}
long long int findMaxAttraction(int N, int start, int D, int attraction[]) {
    n=N,s=start,d=D;
    for (ll i = 0;i < n;i ++)a[i] = attraction[i];
    b.resize(n);
    for (ll i = 0;i < n;i ++)b[i] = a[i];
    sort(b.begin(),b.end());

    b.resize(unique(b.begin(),b.end())-b.begin());
    for (ll i = 0;i < n;i ++)a[i] = lower_bound(b.begin(),b.end(),a[i])-b.begin();
    solve();
//    cout<<"OK"<<endl;
    reverse(a,a+n);
    s=n-1-s;
    solve();
    return res;
}

Compilation message

holiday.cpp: In function 'void solve()':
holiday.cpp:82:30: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   82 |     memset(tree,0,sizeof tree);
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from holiday.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 8664 KB Output is correct
2 Correct 409 ms 8540 KB Output is correct
3 Correct 380 ms 8540 KB Output is correct
4 Correct 383 ms 8536 KB Output is correct
5 Correct 409 ms 8536 KB Output is correct
6 Correct 103 ms 7512 KB Output is correct
7 Correct 209 ms 7772 KB Output is correct
8 Correct 257 ms 8024 KB Output is correct
9 Correct 66 ms 7400 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7184 KB Output is correct
2 Correct 7 ms 7004 KB Output is correct
3 Correct 8 ms 7176 KB Output is correct
4 Correct 14 ms 7188 KB Output is correct
5 Correct 12 ms 7004 KB Output is correct
6 Correct 4 ms 7004 KB Output is correct
7 Correct 4 ms 7004 KB Output is correct
8 Correct 6 ms 7048 KB Output is correct
9 Correct 4 ms 7004 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 8656 KB Output is correct
2 Correct 473 ms 8656 KB Output is correct
3 Correct 307 ms 7772 KB Output is correct
4 Correct 13 ms 7004 KB Output is correct
5 Correct 4 ms 7004 KB Output is correct
6 Correct 4 ms 7168 KB Output is correct
7 Correct 4 ms 7004 KB Output is correct
8 Correct 1058 ms 8492 KB Output is correct
9 Correct 1035 ms 8508 KB Output is correct