Submission #743870

#	Time	Username	Problem	Language	Result	Execution time	Memory
743870		myrcella	Shortcut (IOI16_shortcut)	C++17	100 / 100	1107 ms	57316 KiB

shortcut

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "shortcut.h"
 
const int maxn = 1e6+10;
 
ll pos[maxn];
ll a[maxn];
int n,C;
deque <int> q;
 
bool check(ll k) {
	ll A = 1e18, B = -1e18;
	ll mx1 = 1e18, mn1 = -1e18, mx2 = 1e18, mn2 = -1e18;
	q.clear();
	rep(j,0,n) {
		if (pos[j] + a[j] - A > k) {
			while (!q.empty() and pos[j] + a[j] - (pos[q.front()] - a[q.front()]) > k) {
				B = max(B,pos[q.front()] + a[q.front()]);
				q.pop_front();
			}
			mx1 = min(mx1,k + pos[j] - a[j] + A - C);
			mn1 = max(mn1,pos[j] + a[j] + B - k + C);
			mx2 = min(mx2,k + pos[j] - a[j] - B - C);
			mn2 = max(mn2,pos[j] + a[j] - A - k + C);
		}
		if (mn1 > mx1) return false;
		if (mn2 > mx2) return false;
		while (!q.empty() and pos[q.back()] - a[q.back()] >= pos[j] - a[j]) q.pop_back();
		A = min(A,pos[j] - a[j]);
		q.pb(j);
	}
	int y = 0, z1 = n, z2 = n-1;
	while (y+1<n) {
		while (z2>y and pos[y] + pos[z2] > mx1) z2--;
		if (z2<=y) break;
		while (z1-1>=0 and pos[y] + pos[z1-1] >= mn1) z1--;
		if (z1>z2 or pos[z2] - pos[y] < mn2 or pos[max(z1,y+1)] - pos[y] > mx2) y++;
		else return true;
	}
	return false;
}
 
long long find_shortcut(int N, std::vector<int> L, std::vector<int> d, int c)
{
	n = N; C=c;
	pos[0] = 0;
	rep(i,1,n) pos[i] = pos[i-1] + L[i-1];
	rep(i,0,n) a[i] = d[i];
	ll l = 0,r = 1e16;
	while (l<r) {
		ll mid = (l+r)/2;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
    return l;
}

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