oj.uz

Submission #388633

# Submission time Handle Problem Language Result Execution time Memory
388633 2021-04-12T10:31:15 Z alishahali1382 Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 384 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=1000010;

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;
	pli mn1={INF, 0}, mn2={INF, 0};
	pli mx1={-INF, 0}, mx2={-INF, 0};
	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;
			pli p={X[j]+D[j], j};
			if (p>mx1) swap(mx1, p);
			if (p>mx2) swap(mx2, p);
			
			p={X[j]-D[j], j};
			if (p<mn1) swap(mn1, p);
			if (p<mn2) swap(mn2, p);
		}
		// if (D[i]+X[i]-val<=(X[j]-D[j])) continue ;
		ll mx=(mx1.second==i?mx2.first:mx1.first);
		ll mn=(mn1.second==i?mn2.first:mn1.first);
		X1=max(X1, +X[i]-val+C+D[i] +mx);
		Y1=max(Y1, -X[i]-val+C+D[i] +mx);
		X2=min(X2, +X[i]+val-C-D[i] +mn);
		Y2=min(Y2, -X[i]+val-C-D[i] +mn);
		// AddRect(x+y-z, x-y-z, x+y+z, x-y+z);
	}
	if (X1>X2 || Y1>Y2) return 0;
	int j=0;
	for (int i=1; i<=n; i++){
		ll y=X[i];
		ll l=max(X1-y, Y1+y), r=min(X2-y, Y2+y);
		while (j<n && l<=X[j+1]) j++;
		while (1<j && l<=X[j-1]) j--;
		if (0<=j && j<=n && X[j]<=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 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 332 KB n = 9, 110 is a correct answer
3 Correct 1 ms 332 KB n = 4, 21 is a correct answer
4 Correct 0 ms 332 KB n = 3, 4 is a correct answer
5 Correct 0 ms 332 KB n = 2, 62 is a correct answer
6 Correct 0 ms 332 KB n = 2, 3 is a correct answer
7 Correct 0 ms 332 KB n = 3, 29 is a correct answer
8 Correct 0 ms 332 KB n = 2, 3 is a correct answer
9 Correct 0 ms 332 KB n = 2, 3 is a correct answer
10 Correct 0 ms 332 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 332 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 336 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 332 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 332 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 332 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 336 KB n = 5, 4000000000 is a correct answer
17 Incorrect 1 ms 332 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000317
18 Halted 0 ms 0 KB -