Submission #1032160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032160		kym	Shortcut (IOI16_shortcut)	C++14	38 / 100	2044 ms	4492 KiB

shortcut

#ifndef LOCAL
#include "shortcut.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=3005;
int X[maxn];
vector<int32_t> L, D;
int C;
int n;
const int oo = 1'000'000'000'000'000'000ll;
typedef pair<int,int>pi;
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(pair<uint64_t,uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};

unordered_map<pi,pi,hash_pair>mp;
struct SparseTable {
    vector<vector<int> > ST;
    int N, K;
    SparseTable(int _N, vector<int>a): N(_N) {
        K = MSB(N);
        ST.resize(K);
        ST[0] = a;
        for (int k = 1; k < K; ++k) 
            for (int i = 0; i+(1<<k) <= N; ++i) 
                ST[k].push_back( max(ST[k-1][i], ST[k-1][i+(1<<(k-1))]) ); //min
    }
    
    /* returns most significant bit of an integer */
    inline int MSB(unsigned int x) { return 32-__builtin_clz(x); }
    
    /* Min of range (x, x + 2^k-1) and (y-2^k+1, y) */
    int query(int x, int y) {
        int k = MSB(y-x+1) - 1;
        return max(ST[k][x], ST[k][y-(1<<k)+1]);
    }
    
}*seg1,*seg2;
 
pi get(int L, int R){
	
	int LF = 0, RG = 0;
	int dl=0,dr=0;
	for(int i=0;i<L;i++)dl=max(dl,-X[i]+D[i]);
	for(int i=R+1;i<n;i++)dr=max(dr,X[i]+D[i]);
	int ans=0;
	LF=max(LF,dl+dr+min(X[R]-X[L],C)+X[L]-X[R]);
 
	int m1=0;
	for(int i=L;i<=R;i++){
		m1=max(m1,D[i] + min(X[i]-X[L], X[R]-X[i]+C));
	}
	RG=max(RG,m1 + dl+X[L]);
	int m2=0;
	for(int i=L;i<=R;i++){
		m2=max(m2,D[i] + min(X[R]-X[i], X[i]-X[L]+C));
	}
	LF=max(LF,m2+dr-X[R]);
	int bet=0;
	int idx=L;
	
	
	vector<int> los;
	int mi = L-1;
	for(int i=L+1;i<=R;i++){
		while(mi+1<i){
			int c1= D[i] + D[mi+1] + X[i] - X[mi+1]; // walk
			int c2 = D[i] + D[mi+1] + C + X[mi+1] - X[L] + X[R] - X[i]; // teleport
			if(c2<=c1){
				++mi;
			} else{
				break;
			}

		}
		
		if(L<=mi){
			int wst=seg2->query(L,mi);
			bet=max(bet,C+D[i] - X[i] - X[L] + X[R] + wst);
		}
		if(mi+1<=i-1){
			int wst=seg1->query(mi+1,i-1);
			bet=max(bet,D[i] + X[i] + wst);
		}
	}
	RG=max(RG,bet);
	
	vector<pi> vv1,vv2;
	for(int i=0;i<L;i++){
		vv1.push_back({X[i]+D[i],i});
		vv2.push_back({-X[i]+D[i],i});
	}
	nth_element(vv1.begin(),vv1.begin()+1,vv1.end(),greater<pi>());
	nth_element(vv2.begin(),vv2.begin()+1,vv2.end(),greater<pi>());

	for(int i=0;i<=min(1ll,(int)vv1.size()-1);i++){
		for(int j=0;j<=min(1ll,(int)vv2.size()-1);j++){
			if(vv1[i].second != vv2[j].second){
				LF=max(LF,vv1[i].first+vv2[j].first);
			}
		}
	}
 
	vv1.clear();vv2.clear();
	for(int i=R+1;i<n;i++){
		vv1.push_back({X[i]+D[i],i});
		vv2.push_back({-X[i]+D[i],i});
	}
	nth_element(vv1.begin(),vv1.begin()+1,vv1.end(),greater<pi>());
	nth_element(vv2.begin(),vv2.begin()+1,vv2.end(),greater<pi>());

	for(int i=0;i<=min(1ll,(int)vv1.size()-1);i++){
		for(int j=0;j<=min(1ll,(int)vv2.size()-1);j++){
			if(vv1[i].second != vv2[j].second){
				LF=max(LF,vv1[i].first+vv2[j].first);
			}
		}
	}
 
	return {LF,RG};
}
long long find_shortcut(int32_t n, vector<int32_t> l, vector<int32_t> d, int32_t c)
{
	L=l;D=d;C=c;
	::n=n;
	for(int i=1;i<n;i++){
		X[i]=X[i-1]+l[i-1];
	}  
	vector<int>c1=vector<int>(n+1,-oo);
	vector<int>c2=vector<int>(n+1,-oo);
	for(int i=0;i<n;i++){
		c1[i]=-X[i]+D[i];
		c2[i]=X[i]+D[i];
	}
	seg1=new SparseTable(n+1,c1);
	seg2=new SparseTable(n+1,c2);

	int ans=oo;
	
	for(int i=0;i<n;i++){
		vector<int> vec;
		int lo = i,hi=n;
		while(lo<hi-1){
			int mi=(lo+hi)/2;
			pi hh=get(i,mi);
			ans=min(ans,max(hh.first,hh.second));
			if(hh.first<=hh.second){//we should move right more
				hi=mi;
			} else{
				lo=mi;
			}
		}
		
		
	}

	return ans;
}
#ifdef LOCAL
 
int32_t main()
{
	int32_t n, c;
	assert(2 == scanf("%d%d", &n, &c));
	
	std::vector<int32_t> l(n - 1);
	std::vector<int32_t> d(n);
	for (int i = 0; i < n - 1; i++)
		assert(1 == scanf("%d", &l[i]));
	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &d[i]));
		
	long long t = find_shortcut(n, l, d, c);
	
	
	printf("%lld\n", t);
	
	return 0;
}
 
#endif

Compilation message (stderr)

shortcut.cpp: In function 'pi get(long long int, long long int)':
shortcut.cpp:57:6: warning: unused variable 'ans' [-Wunused-variable]
   57 |  int ans=0;
      |      ^~~
shortcut.cpp:71:6: warning: unused variable 'idx' [-Wunused-variable]
   71 |  int idx=L;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3