oj.uz

Submission #388598

# Submission time Handle Problem Language Result Execution time Memory
388598 2021-04-12T08:28:56 Z alishahali1382 Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 332 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const ll INF=10000001000000000ll;
const int MAXN=100010;

int n, m, k;
ll L[MAXN], D[MAXN], X[MAXN], C, ans;
pli XD[MAXN]; // X-D
pli DX[MAXN]; // D+X
ll X1, Y1, X2, Y2;

bool Check(ll val){
	X1=Y1=-INF;
	X2=Y2=INF;
	ll mn1=INF, mx1=-INF, mn2=INF, mx2=-INF;
	int jj=1;
	for (int ii=1; ii<=n; ii++){
		int i=DX[ii].second;
		while (jj<=n && DX[ii].first-val>XD[jj].first){
			int j=XD[jj++].second;
			mn1=min(mn1, X[j]+D[j]);
			mx1=max(mx1, X[j]+D[j]);
			mn2=min(mn2, X[j]-D[j]);
			mx2=max(mx2, X[j]-D[j]);
		}
		// if (D[i]+X[i]-val<=(X[j]-D[j])) continue ;
		X1=max(X1, +X[i]-val+C+D[i] +mx1);
		Y1=max(Y1, -X[i]-val+C+D[i] +mx1);
		X2=min(X2, +X[i]+val-C-D[i] +mn2);
		Y2=min(Y2, -X[i]+val-C-D[i] +mn2);
		// AddRect(x+y-z, x-y-z, x+y+z, x-y+z);
	}
	for (int i=1; i<=n; i++){
		ll y=X[i];
		ll l=max(X1-y, Y1+y), r=min(X2-y, Y2+y);
		int pos=lower_bound(X+1, X+n+1, l)-X;
		if (pos<=n && X[pos]<=r) return 1;
	}
	return 0;
}

ll find_shortcut(int _n, vector<int> l, vector<int> d, int _C){
	n=_n;
	C=_C;
	for (int i=1; i<n; i++) L[i]=l[i-1], X[i+1]=X[i]+L[i];
	for (int i=1; i<=n; i++){
		D[i]=d[i-1];
		XD[i]={X[i]-D[i], i};
		DX[i]={D[i]+X[i], i};
	}
	sort(XD+1, XD+n+1);
	sort(DX+1, DX+n+1);

	ll dwn=-1, up=INF;
	while (up-dwn>1){
		ll mid=(dwn+up)>>1;
		if (Check(mid)) up=mid;
		else dwn=mid;
	}
	return up;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 0 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 204 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 204 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -