oj.uz

Submission #399205

# Submission time Handle Problem Language Result Execution time Memory
399205 2021-05-05T12:15:27 Z MarcoMeijer Holiday (IOI14_holiday) C++14
100 / 100
 1743 ms 6204 KB 
#include <bits/stdc++.h>
#ifndef DEBUG
#include "holiday.h"
#endif
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<17);

vi a, sa, ra;
int n, start, d;

// segment tree
ll TOT[N*2], SUM[N*2];
void setSeg(int i, ll v, int l=0, int r=N-1, int p=1) {
    if(i < l || i > r) return;
    if(l == r) {
        TOT[p] = v ? 1 : 0;
        SUM[p] = v;
        return;
    }
    int m=(l+r)/2;
    setSeg(i,v,l  ,m,p*2  );
    setSeg(i,v,m+1,r,p*2+1);
    TOT[p] = TOT[p*2] + TOT[p*2+1];
    SUM[p] = SUM[p*2] + SUM[p*2+1];
}
ll getSeg(int x, int l=0, int r=N-1, int p=1) {
    if(x <= 0) return 0;
    if(TOT[p] <= x) return SUM[p];

    int m=(l+r)/2;
    if(TOT[p*2+1] <= x) {
        return SUM[p*2+1] + getSeg(x-TOT[p*2+1], l, m, p*2);
    } else {
        return getSeg(x, m+1, r, p*2+1);
    }
}

void addX(int x) {
    setSeg(ra[x],a[x]);
}
void removeX(int x) {
    setSeg(ra[x],0);
}

ll daq(int l, int r, int al, int ar) {
    // r <= al
    // everything between [r,al] is placed
    if(l > r) return 0;
    int mid=(l+r)/2;

    REP(i,mid,r) addX(i);

    ll res=0, bestM=al;
    REP(i,al,ar+1) {
        addX(i);
        ll used = start + i - mid*2;
        if(used >= d) break;
        ll nRes = getSeg(d - used);
        if(nRes > res) {
            bestM = i;
            res = nRes;
        }
    }
    REP(i,al+1,ar+1) removeX(i);
    
    addX(mid-1);
    res = max(res, daq(l,mid-1,al,bestM));
    REP(i,mid-1,r) removeX(i);

    REP(i,al+1,bestM+1) addX(i);
    res = max(res, daq(mid+1,r,bestM,ar));
    REP(i,al+1,bestM+1) removeX(i);

    return res;
}
ll solve() {
    sa.resize(n);
    RE(i,n) sa[i]=i;
    sort(all(sa),[](int i, int j) {
        return a[i] < a[j];
    });

    ra.resize(n);
    RE(i,n) ra[sa[i]] = i;

    RE(i,N*2) TOT[i] = SUM[i] = 0;

    addX(start);
    return daq(0,start,start,n-1);
}
ll findMaxAttraction(int _n, int _start, int _d, int attraction[]) {
    n = _n; start = _start; d = _d;
    RE(i,n) a.pb(attraction[i]);

    ll res = 0;
    RE(_,2) {
        res = max(res, solve());
        // reverse everything
        start = n - start - 1;
        reverse(all(a));
    }
    return res;
}


#ifdef DEBUG
int _n, D, Start, Att[100000];
int main() {
    cin>>_n>>Start>>D;
    RE(i,_n) cin>>Att[i];
    cout<<findMaxAttraction(_n,Start,D,Att)<<endl;
}
#endif

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 6084 KB Output is correct
2 Correct 478 ms 6092 KB Output is correct
3 Correct 538 ms 6084 KB Output is correct
4 Correct 476 ms 6092 KB Output is correct
5 Correct 598 ms 5996 KB Output is correct
6 Correct 164 ms 4812 KB Output is correct
7 Correct 315 ms 5328 KB Output is correct
8 Correct 372 ms 5448 KB Output is correct
9 Correct 114 ms 4724 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4428 KB Output is correct
2 Correct 15 ms 4428 KB Output is correct
3 Correct 16 ms 4464 KB Output is correct
4 Correct 37 ms 4460 KB Output is correct
5 Correct 34 ms 4432 KB Output is correct
6 Correct 10 ms 4428 KB Output is correct
7 Correct 11 ms 4428 KB Output is correct
8 Correct 11 ms 4428 KB Output is correct
9 Correct 11 ms 4428 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 6052 KB Output is correct
2 Correct 532 ms 6204 KB Output is correct
3 Correct 520 ms 5248 KB Output is correct
4 Correct 29 ms 4428 KB Output is correct
5 Correct 11 ms 4428 KB Output is correct
6 Correct 11 ms 4300 KB Output is correct
7 Correct 11 ms 4428 KB Output is correct
8 Correct 1732 ms 6164 KB Output is correct
9 Correct 1743 ms 6036 KB Output is correct