Submission #288309

#	Time	Username	Problem	Language	Result	Execution time	Memory
288309		egekabas	휴가 (IOI14_holiday)	C++14	47 / 100	5011 ms	11036 KiB

holiday

//#include "grader.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct tree{
    vector<ll> seg;
    void init(ll n){
        seg.resize(4*n+9);
    }
    void upd(ll v, ll tl, ll tr, ll idx, ll val){
        if(tl == idx && tr == idx){
            seg[v] += val;
            return;
        }
        if(idx <= (tl+tr)/2)
            upd(2*v, tl, (tl+tr)/2, idx, val);
        else
            upd(2*v+1, (tl+tr)/2+1, tr, idx, val);
        seg[v] = seg[2*v]+seg[2*v+1];
    }
    pll get(ll v, ll tl, ll tr, ll val){
        if(tl == tr)
            return {tl, max(0LL, seg[v]-val)};
        if(seg[2*v+1] >= val)
            return get(2*v+1, (tl+tr)/2+1, tr, val);
        else
            return get(2*v, tl, (tl+tr)/2, val-seg[2*v+1]);
    }
};
struct bit{
    ll n;
    vector<ll> bit;
    void init(ll sz){
        bit.resize(sz+1);
        n = sz;
    }
    void upd(ll idx, ll val){
        for(++idx; idx > 0; idx -= idx&(-idx))
            bit[idx] += val;
    }
    ll get(ll idx){
        ll ret = 0;
        for(++idx; idx <= n; idx += idx&(-idx))
            ret += bit[idx];
        return ret;
    }
};
vector<ll> mpp;
ll maxn;
ll get(ll x){
    return lower_bound(all(mpp), x)-mpp.begin();
}
int N, D;

ll getval(vector<ll> v, ll lim){
    tree s;
    bit b;
    s.init(maxn);
    b.init(maxn);
    ll ans = 0;
    for(int i = 0; i < v.size(); ++i){
        s.upd(1, 0, maxn-1, v[i], 1);
        b.upd(v[i], mpp[v[i]]);
        if(lim-i <= 0) break;
        pll idx = s.get(1, 0, maxn-1, lim-i);
        //cout << i << ' ' << mpp[idx.ff] << '\n';
        ans = max(ans, b.get(idx.ff)-mpp[idx.ff]*idx.ss);
    }
    return ans;
}
vector<ll> getvec(vector<ll> v, ll come){
    vector<ll> ret(D);
    vector<ll> s;
    for(ll i = 0; i < v.size(); ++i){
        s.insert(lower_bound(all(s), v[i], greater<ll>()), v[i]);
        ll cost = i;
        if(come)
            cost *= 2;
        ll val = 0;
        for(auto u : s){
            ++cost;
            val += u;
            if(cost >= D) break;
            ret[cost] = max(ret[cost], val);
        }
    }
    for(ll i = 1; i < ret.size(); ++i)
        ret[i] = max(ret[i-1], ret[i]);
    return ret;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    N = n;
    D = d;
    for(int i = 0; i < n; ++i)
        mpp.pb(attraction[i]);
    sort(all(mpp));
    mpp.resize(unique(all(mpp))-mpp.begin());
    maxn = mpp.size();
    for(int i = 0; i < n; ++i)
        attraction[i] = get(attraction[i]);
    if(start == 0){
        vector<ll> v;
        for(int i = 0; i < n; ++i)
            v.pb(attraction[i]);
        return getval(v, d);
    }
    vector<ll> v1, v2, v3, v4;
    for(ll i = start; i < n; ++i)
        v1.pb(mpp[attraction[i]]);
    for(ll i = start+1; i < n; ++i)
        v2.pb(mpp[attraction[i]]);
    for(ll i = start; i >= 0; --i)
        v3.pb(mpp[attraction[i]]);
    for(ll i = start-1; i >= 0; --i)
        v4.pb(mpp[attraction[i]]);
    vector<ll> go1, come1, go2, come2;
    go1 = getvec(v2, 0);
    come1 = getvec(v1, 1);
    go2 = getvec(v4, 0);
    come2 = getvec(v3, 1);
    ll ans = 0;
    for(ll i = 0; i < d; ++i){
        ans = max(ans, come1[i]+go2[d-i-1]);
        ans = max(ans, come2[i]+go1[d-i-1]);
    }
    vector<ll> v;
    for(int i = start; i < n; ++i)
        v.pb(attraction[i]);
    ans = max(ans, getval(v, d));
    
    v.clear();
    for(int i = start; i >= 0; --i)
        v.pb(attraction[i]);
    ans = max(ans, getval(v, d));
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'll getval(std::vector<long long int>, ll)':
holiday.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 0; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
holiday.cpp: In function 'std::vector<long long int> getvec(std::vector<long long int>, ll)':
holiday.cpp:85:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(ll i = 0; i < v.size(); ++i){
      |                   ~~^~~~~~~~~~
holiday.cpp:98:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(ll i = 1; i < ret.size(); ++i)
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53