oj.uz

Submission #643611

# Submission time Handle Problem Language Result Execution time Memory
643611 2022-09-22T15:45:27 Z jiahng Holiday (IOI14_holiday) C++14
100 / 100
 3054 ms 47856 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 300010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,D,S,A[maxn];

int disc[maxn], undisc[maxn];
int F[maxn],G[maxn];
struct node{
    int s,e,m,val=0,num=0;
    node *l,*r;

    node(int ss,int ee){
        s = ss; e = ee; m = (s + e) / 2;
        if (s != e){
            l = new node(s,m); r = new node(m+1,e);
        }
    }
    void upd(int p,int v){
        if (s == e){
            val += undisc[s] * v; num += v;
        }else{
            if (p > m) r->upd(p, v);
            else l->upd(p,v);
            val = l->val + r->val;
            num = l->num + r->num;
        }
    }
    int qry(int v){
        if (s == e) return (v > 0) * val;
        if (r->num < v) return r->val + l->qry(v-r->num);
        else return r->qry(v);
    }
    void clear(){
        val = num = 0;
        if (s != e){
            l->clear(); r->clear();
        }
    }
}*root;
int M;
int Fval[maxn], Gval[maxn];
void dnc(int l,int r,int vl,int vr){
   // root is at vl-1
    if (l > r) return; 
    int m = (l + r) / 2;
    F[m] = vl; int cur = -1;
    FOR(i,vl,vr){ // s to i
        root->upd(disc[i], 1);
        int val = root->qry(m - (i - S));
        if (val > cur){
            cur = val; F[m] = i;
        }
    }
    //cout << m << ' ' << cur << '\n';
    Fval[m] = cur;
    FOR(i,F[m],vr) root->upd(disc[i], -1);
    dnc(m+1,r,F[m],vr);
    FOR(i,vl,F[m]-1) root->upd(disc[i], -1);
    dnc(l,m-1,vl,F[m]);
}

void backdnc(int l,int r,int vl,int vr){
   // root is at vr+1
    if (l > r) return; 
    int m = (l + r) / 2;
    G[m] = vr; int cur = -1;
    DEC(i,vr,vl){ // i to s
        root->upd(disc[i], 1);
        int val = root->qry(m - (S-1 - i));
        if (val > cur){
            cur = val; G[m] = i;
        }
    }
    //cout << m << ' ' << Gval[m] << ' ' << cur << '\n';
    Gval[m] = cur;
    FOR(i,vl,G[m]) root->upd(disc[i], -1);
    backdnc(m+1,r,vl,G[m]);
    FOR(i,G[m]+1,vr) root->upd(disc[i], -1);
    backdnc(l,m-1,G[m],vr);
}       
int B[maxn];
int solve(){
    vi v2;
    FOR(i,0,S) v2.pb(B[i]);
    FOR(i,S+1,N-1){v2.pb(0); v2.pb(B[i]);} // model return moves
    M = v2.size();
    FOR(i,0,M-1) A[i] = v2[i];
    vpi v;
    FOR(i,0,M-1) v.pb(pi(A[i], i));
    sort(all(v)); 
    FOR(i,0,M-1){
        disc[v[i].s] = i; undisc[i] = v[i].f;
    }

    root->clear();
    dnc(0, D, S, M-1);
    root->clear();
    backdnc(0,D,0,S-1);

    int ans = max(Fval[D], Gval[D-1]);
    
    FOR(i,0,D){ // number of days spent going right
        if (D - i - 1 >= 0){
            ans = max(ans, Gval[D - i -1] + Fval[i]);
        }
    }
    return ans;
}
    
ll findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
    N = n; D = d; S = start;
    root = new node(0,2*N-1);
    FOR(i,0,N-1) B[i] = attraction[i];
    int ans = solve();
    reverse(B, B+N);
    S = N - 1 - S;
    ans = max(ans, solve());
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 42300 KB Output is correct
2 Correct 1579 ms 42320 KB Output is correct
3 Correct 1524 ms 42256 KB Output is correct
4 Correct 1602 ms 42248 KB Output is correct
5 Correct 1922 ms 37188 KB Output is correct
6 Correct 641 ms 16480 KB Output is correct
7 Correct 1004 ms 21564 KB Output is correct
8 Correct 1190 ms 25328 KB Output is correct
9 Correct 535 ms 15428 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2116 KB Output is correct
2 Correct 29 ms 2040 KB Output is correct
3 Correct 32 ms 2116 KB Output is correct
4 Correct 31 ms 1864 KB Output is correct
5 Correct 27 ms 1840 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 8 ms 1108 KB Output is correct
9 Correct 8 ms 1084 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1580 ms 47856 KB Output is correct
2 Correct 1543 ms 43784 KB Output is correct
3 Correct 897 ms 18240 KB Output is correct
4 Correct 25 ms 1844 KB Output is correct
5 Correct 7 ms 1116 KB Output is correct
6 Correct 7 ms 1080 KB Output is correct
7 Correct 7 ms 1076 KB Output is correct
8 Correct 3054 ms 40084 KB Output is correct
9 Correct 2947 ms 40104 KB Output is correct