oj.uz

Submission #980011

# Submission time Handle Problem Language Result Execution time Memory
980011 2024-05-11T19:15:06 Z thomas_li Holiday (IOI14_holiday) C++17
77 / 100
 1241 ms 12984 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A,class B> void cmx(A& x, B y) {x=max<A>(x,y);}
template<class A,class B> void cmn(A& x, B y) {x=min<A>(x,y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) { // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) { // sum of values in [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
		// Returns n if no sum is >= sum, or -1 if empty sum is.
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1 << 25; pw; pw >>= 1) {
			if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
				pos += pw, sum -= s[pos-1];
		}
		return pos;
	}
};
typedef vector<ll> vll;
vll calc(vi& a, int mul, int len, int base = 0){
    int n = sz(a);
    vll res(len);
    if(!n) return res;
    vi vals = a; sort(all(vals),greater<>()); vals.erase(unique(all(vals)),vals.end());
    FT cnt(sz(vals)),sum(sz(vals));
    auto add = [&](int x, int v){
        int pos = lower_bound(all(vals),x,greater<>())-vals.begin();
        cnt.update(pos,v);  
        sum.update(pos,v*x);
    };
    auto qry = [&](int num){
        if(num <= 0) return 0ll;
        int pos = cnt.lower_bound(num+1);
        ll ext = num-cnt.query(pos);
        /*
        if(ext < 0){
            cerr << "WUT " << num << " " << ext << "\n";
            exit(0);
        }*/
        assert(ext >= 0); 
        //int cnext = (pos == sz(cnt.s) ? 0 : cnt.query(pos+1)-cnt.query(pos));
        ll cur = sum.query(pos); 
        if(pos < sz(vals)) cur += ext * vals[pos]; 
        return cur;
    };
    auto rec = [&](auto&& rec, int l, int r, int optl, int optr){
        if(l > r) return; 
        int mid = (l+r)/2; pair<ll,int> ans{-1,0};
        for(int i = optl; i <= optr; i++){
            int rem = mid-(i+base)*mul;
            add(a[i],1); 
            cmx(ans,pair<ll,int>{qry(rem),i});         
        } 
        assert(ans.FS >= 0);
        res[mid] = ans.FS; //ans.SD *= -1;
        for(int i = optr; i >= ans.SD; i--){
            add(a[i],-1);
        } 
        rec(rec,mid+1,r,ans.SD,optr);
        for(int i = ans.SD-1; i >= optl; i--){
            add(a[i],-1);
        } 
        rec(rec,l,mid-1,optl,ans.SD);
    };
    rec(rec,0,sz(res)-1,0,n-1);
    return res;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]){
    vi a{attraction,attraction+n};
    vi rit{a.begin()+s,a.end()};
    vi lft{a.begin(),a.begin()+s};
    reverse(all(lft));
    auto rf = calc(rit,2,3*n);
    auto rs = calc(rit,1,3*n);
    auto lf = calc(lft,2,3*n,1);
    auto ls = calc(lft,1,3*n,1);
    ll ans = 0;
    rep(i,0,d+1){
        cmx(ans,rf[i]+ls[d-i]);
        cmx(ans,rs[i]+lf[d-i]);
    }
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 11488 KB Output is correct
2 Correct 57 ms 11580 KB Output is correct
3 Correct 157 ms 11328 KB Output is correct
4 Correct 104 ms 11328 KB Output is correct
5 Correct 373 ms 10560 KB Output is correct
6 Runtime error 107 ms 7252 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1084 KB Output is correct
2 Correct 5 ms 1116 KB Output is correct
3 Correct 16 ms 1116 KB Output is correct
4 Correct 18 ms 980 KB Output is correct
5 Correct 16 ms 1148 KB Output is correct
6 Correct 5 ms 856 KB Output is correct
7 Correct 6 ms 1064 KB Output is correct
8 Correct 6 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12108 KB Output is correct
2 Correct 839 ms 12320 KB Output is correct
3 Correct 488 ms 6224 KB Output is correct
4 Correct 19 ms 1120 KB Output is correct
5 Correct 5 ms 864 KB Output is correct
6 Correct 6 ms 928 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 1241 ms 12984 KB Output is correct
9 Correct 1209 ms 12520 KB Output is correct