Submission #595321

#	Time	Username	Problem	Language	Result	Execution time	Memory
595321		LastRonin	Shortcut (IOI16_shortcut)	C++14	31 / 100	2082 ms	460 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pill pair<ll, ll>
#define mp make_pair
#define f first
#define s second
using namespace std;

const ll N = 3e5;

int n, c;
ll le[N];
ll d[N];
ll pr[N];
ll precPr[N];
ll precSuf[N];

struct seg {
	ll t[4 * N] = {0};
	ll p[4 * N] = {0};
	void push(ll v, ll tl, ll tr) {
		t[v] = t[v] + p[v];
		if(tl < tr) {
			p[v * 2] += p[v];
			p[v * 2 + 1] += p[v];
		}
	   	p[v] = 0;
	}
	void upd(ll p, ll z, ll v = 1, ll tl = 0, ll tr = n) {
		push(v, tl, tr);
		if(tl == tr) {
			t[v] = z;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m) {
			upd(p, z, v * 2, tl, m);
			push(v * 2 + 1, m + 1, tr);	
		} else {
			upd(p, z, v * 2 + 1, m + 1, tr);
			push(v * 2, tl, m);
		}
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	void dob(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = n) {
		push(v, tl, tr);
		if(l > tr || tl > r)return;
		if(l <= tl && tr <= r) {
			p[v] += z;
			push(v, tl, tr);
			return;
		}
		ll m = (tl + tr) >> 1ll;
		dob(l, r, z, v * 2, tl, m);
		dob(l, r, z, v * 2 + 1, m + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	ll get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = n) {
	    push(v, tl, tr);
		if(l > tr || tl > r)return 0;
		if(l <= tl && tr <= r)return t[v];
		ll m = (tl + tr) >> 1ll;
		return max(get(l, r, v * 2, tl, m), get(l, r, v * 2 + 1, m + 1, tr));
	}
} rt[3];

ll calc(ll l, ll r) {
    ll sub = 0;
    for(int i = 0; i < n; i++)
    	sub = max(sub, d[i]);
	for(int i = 0; i < l; i++) {
		for(int j = i + 1; j < l; j++) {
			sub = max(sub, pr[j] - pr[i] + d[i] + d[j]);
		}
	}
	for(int i = r; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			sub = max(sub, pr[j] - pr[i] + d[i] + d[j]);
		}
	}
	for(int i = 0; i < l; i++) {
		for(int j = r + 1; j < n; j++) {
			sub = max(sub, d[i] + d[j] + pr[l] - pr[i] + pr[j] - pr[r] + min((ll)c, pr[r] - pr[l]));
		}
	}	
	for(int i = 0; i < l; i++) {
		for(int j = l; j <= r; j++) {
			ll dist = (pr[l] - pr[i]) + min(c + pr[r] - pr[j], pr[j] - pr[l]) + d[i] + d[j];
			sub = max(sub, dist);			
		}
	}
	for(int j = l; j <= r; j++) {
		for(int i = r + 1; i < n; i++) {
			ll dist = (pr[i] - pr[r]) + min(c + pr[j] - pr[l], pr[r] - pr[j]) + d[i] + d[j];
			sub = max(sub, dist);
		}
	}
	for(int i = l; i < r; i++) {
		for(int j = i + 1; j <= r; j++) {
			ll dist = min(pr[j] - pr[i], pr[i] - pr[l] + pr[r] - pr[j] + c) + d[i] + d[j];
			sub = max(sub, dist);
		}
	}
	return sub;
}

ll find_shortcut(int na, vector<int> l, vector<int> di, int C) {
	c = C;
	n = na;
	for(int i = 0; i < n - 1; i++) {
		le[i + 1] = l[i];		
	}
	pr[0] = 0;
	for(int i = 1; i < n; i++)
		pr[i] = pr[i - 1] + le[i];
	for(int i = 0; i < n; i++)
		d[i] = di[i];
	for(int i = 0; i < n; i++) {
		rt[0].upd(i, pr[i] - d[i]);
		rt[1].upd(i, pr[i] + d[i]);
	}
	ll ans = calc(0, 1);
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			ans = min(ans, calc(i, j));		
		}
	}
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int calc(long long int, long long int)':
shortcut.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |     for(int i = 0; i < n; i++)
      |     ^~~
shortcut.cpp:73:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |  for(int i = 0; i < l; i++) {
      |  ^~~

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