Submission #1032116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032116		kym	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	604 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;
map<pi,pi>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){
	if(mp.find({L,R}) != mp.end())return mp[make_pair(L,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;
	
	
	
	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);
		}
	}
	RG=max(RG,bet);
	
	priority_queue<pi,vector<pi>,greater<pi>> vm1,vm2;
	for(int i=0;i<L;i++){
		vm1.push({X[i]+D[i],i});
		vm2.push({-X[i]+D[i],i});
		while(vm1.size()>2)vm1.pop();
		while(vm2.size()>2)vm2.pop();
	}
	vector<pi>vv1,vv2;
	while(vm1.size()){
		vv1.push_back(vm1.top());vm1.pop();
	}
	while(vm2.size()){
		vv2.push_back(vm2.top());vm2.pop();
	}
	sort(vv1.begin(),vv1.end(),greater<pi>());
	sort(vv2.begin(),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);
			}
		}
	}
 
	for(int i=R+1;i<n;i++){
		vm1.push({X[i]+D[i],i});
		vm2.push({-X[i]+D[i],i});
		while(vm1.size()>2)vm1.pop();
		while(vm2.size()>2)vm2.pop();
	}
	vv1.clear();vv2.clear();
	while(vm1.size()){
		vv1.push_back(vm1.top());vm1.pop();
	}
	while(vm2.size()){
		vv2.push_back(vm2.top());vm2.pop();
	}
	sort(vv1.begin(),vv1.end(),greater<pi>());
	sort(vv2.begin(),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;
	vector<int> los;
	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;
			}
		}
		los.push_back(lo);
		
		for(int j=lo;j<hi;j++){
			if(j<=i)continue;
			if(j>=n)continue;
			pi hh=get(i,j);
 
			ans=min(ans,max(hh.first,hh.second));
		}
	}
	for(int i=0;i<(int)los.size()-1;i++){
		assert(los[i]<=los[i+1]);
	}
 
	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: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3