Submission #1305336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305336		thelegendary08	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	344 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define int long long 
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
struct segtree{
	vi tree; int n;
	segtree(int x){
		n = x; tree.resize(2*n+5); 
	}
	void update(int k, int x){
		k+=n; tree[k]=x; for(k/=2;k>=1;k/=2){
			tree[k]=max(tree[k*2],tree[k*2+1]);
		}
	}
	int quer(int l, int r){
		l+=n; r+=n; int ret = -4e18; while(l <= r){
			if(l%2)ret=max(ret,tree[l++]); if(r%2==0)ret=max(ret,tree[r--]);
			l/=2;r/=2;
		} return ret;
	}
};
long long find_shortcut(signed n, std::vector<signed> ll, std::vector<signed> dd, signed cc)
{
	vi p(n); FOR(i,1,n)p[i]=p[i-1]+ll[i-1]; vi d(n); f0r(i,n)d[i]=dd[i]; int C = cc; vector<pair<int,pair<int,int>>>w; 
	f0r(l,n)FOR(r,l+1,n){
		w.pb(mp((p[r]-p[l]+C)/2,mp(l,r)));
	} sort(w.begin(),w.end()); 
	segtree S1 = segtree(n), S2 = segtree(n); 
	f0r(i,n)S1.update(i, d[i]+p[i]), S2.update(i, d[i]-p[i]); 
	int ans = 0; f0r(l,n)FOR(r,l+1,n)ans=max(ans, p[r]-p[l]+d[r]+d[l]);
	vi pref(n), suf(n); pref[0]=d[0]-p[0]; FOR(i,1,n)pref[i]=max(pref[i-1],d[i]-p[i]);
	suf[n-1]=d[n-1]+p[n-1]; for(int i = n-2; i >= 0; i--)suf[i]=max(suf[i+1], d[i]+p[i]);
	f0r(tt,w.size()){
		int T=w[tt].first,x=w[tt].second.first,y=w[tt].second.second,D=p[y]-p[x]; if(D <= C)continue;
		//case 1
		int cur = pref[x] + suf[y] + C - D;// dout(cur);
		//case 2l 
		int lo = x, hi = y; while(lo < hi){
			int mid = lo + (hi - lo) / 2;
			if(C + p[y] - p[mid] < p[mid] - p[x])hi = mid; else lo = mid + 1; 
		}
		int lef = pref[x] + S1.quer(x,lo-1);
		int rig = pref[x] + p[x] + S2.quer(lo,y) + C + p[y]; 
		cur = max(cur, max(lef, rig));
		//case 2r
		lo = x, hi = y; while(lo < hi){
			int mid = lo + (hi - lo + 1) / 2; 
			if(C + p[mid] - p[x] < p[y] - p[mid])lo = mid; 
			else hi = mid - 1; 
		}
		lef = suf[y] + C - p[x] - p[y] + S1.quer(x, lo); 
		rig = suf[y] + S2.quer(lo+1, y); 
		cur = max(cur, max(lef,rig));
		//case 3
		for(int l = x+1; l < y; l++)for(int r = l+1; r < y; r++){
			cur = max(cur, d[l] + d[r] + min(p[r] - p[l], D + C - (p[r] - p[l])));
		}
		ans = min(ans,cur);
	}
    return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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