Submission #1031966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031966		kym	Shortcut (IOI16_shortcut)	C++14	38 / 100	2033 ms	1400 KiB

shortcut

#ifndef LOCAL
#include "shortcut.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=3005;
const int LOG=11;
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 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]);
    }
    
};

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>c1=vector<int>(n+1,-oo);
	vector<int>c2=vector<int>(n+1,-oo);
	for(int i=L;i<=R;i++){
		c1[i]=-X[i]+D[i];
		c2[i]=X[i]+D[i];
	}
	SparseTable seg1=SparseTable(n+1,c1);
	SparseTable seg2=SparseTable(n+1,c2);
	
	/*
	for(int i=L+1;i<=R;i++){
		int lo = L-1, hi=i;
		while(lo<hi-1){
			int mi=(lo+hi)/2;
			int c1= D[i] + D[mi] + X[i] - X[mi]; // walk
			int c2 = D[i] + D[mi] + C + X[mi] - X[L] + X[R] - X[i]; // teleport
			
			if(c2<=c1){
				lo=mi;
			} else{
				hi=mi;
			}
		}
		
		if(L<=lo){
			int wst=seg2.query(L,lo);
			
			bet=max(bet,C+D[i] - X[i] - X[L] + X[R] + wst);
			
		}
		if(lo+1<=i-1){
			
			int wst=seg1.query(lo+1,i-1);
			
			bet=max(bet,D[i] + X[i] + wst);
		}
	}*/
	for(int i=L;i<=R;i++){
		for(int j=i+1;j<=R;j++){
			bet=max(bet,D[i]+D[j]+min(X[j]-X[i],C+X[i]-X[L]+X[R]-X[j]));
		}
	}
	//cerr<<bet<<"\n";
	RG=max(RG,bet);
	
	vector<pi> vm1,vm2;
	for(int i=0;i<L;i++){
		vm1.push_back({X[i]+D[i],i});
		vm2.push_back({-X[i]+D[i],i});
 
 
	}
	sort(vm1.begin(),vm1.end(),greater<pi>());
	sort(vm2.begin(),vm2.end(),greater<pi>());
	for(int i=0;i<=min(1ll,(int)vm1.size()-1);i++){
		for(int j=0;j<=min(1ll,(int)vm2.size()-1);j++){
			if(vm1[i].second != vm2[j].second){
				LF=max(LF,vm1[i].first+vm2[j].first);
			}
		}
	}
 
	vm1.clear();
	vm2.clear();
	for(int i=R+1;i<n;i++){
		vm1.push_back({X[i]+D[i],i});
		vm2.push_back({-X[i]+D[i],i});
	}
	sort(vm1.begin(),vm1.end(),greater<pi>());
	sort(vm2.begin(),vm2.end(),greater<pi>());
	for(int i=0;i<=min(1ll,(int)vm1.size()-1);i++){
		for(int j=0;j<=min(1ll,(int)vm2.size()-1);j++){
			if(vm1[i].second != vm2[j].second){
				LF=max(LF,vm1[i].first+vm2[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];
	}  
	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;
			}
		}
		
		//cerr<<i<<":"<<endl;
		for(int j=lo-1;j<hi+1;j++){
			if(j<=i)continue;
			if(j>=n)continue;
			pi hh=get(i,j);
			//cerr<<hh.first<<" "<<hh.second<<endl;
			ans=min(ans,max(hh.first,hh.second));
		}
	}
 
	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:44:6: warning: unused variable 'ans' [-Wunused-variable]
   44 |  int ans=0;
      |      ^~~
shortcut.cpp:58:6: warning: unused variable 'idx' [-Wunused-variable]
   58 |  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