oj.uz

Submission #24506

# Submission time Handle Problem Language Result Execution time Memory
24506 2017-06-09T14:12:25 Z Jeyeon Si(#1042) Shortcut (IOI16_shortcut) C++
0 / 100
 636 ms 73816 KB 
#include "shortcut.h"
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

int n;
ll c;
ll ps[1000100], d[1000100];
ll pspd[1000100], ord[1000100], rord[1000100];

const pll mM = pll(-(1LL<<52),(1LL<<52));
pll tree[2100100]; // ps+d�� �ִ�, ps-d�� �ּ�
int key = 1048576;

pll mer(pll a, pll b) {
	return pll(max(a.first,b.first),min(a.second,b.second));
}

void upd(int idx, pll tmp) {
	idx += key;
	while(idx>0) {
		tree[idx] = mer(tree[idx],tmp);
		idx/=2;
	}
}

pll getv(int s, int e) {
	pll tmp = mM;
	s+=key;e+=key;
	while(s<=e) {
		if (s%2==1) tmp = mer(tmp,tree[s++]);
		if (e%2==0) tmp = mer(tmp,tree[e--]);
		s>>=1;e>>=1;
	}
	return tmp;
}

set<ll> s;
bool ok(ll t) {
	int i;
	pll a = mM, b = mM, tmp; // x+y, y-x
	for (i=0;i<key*2;i++) tree[i] = mM;
	for (i=n-1;i>=0;i--) {
		int idx = lower_bound(pspd,pspd+n,ps[i]-d[i]+t+1)-pspd;
		tmp = getv(idx,n-1);
		b = mer(b,pll(tmp.first-t+c-(ps[i]-d[i]),tmp.second+t-c-(ps[i]+d[i])));
		a = mer(a,pll(tmp.first-t+c+(ps[i]+d[i]),tmp.second+t-c+(ps[i]-d[i])));
		upd(rord[i],pll(ps[i]+d[i],ps[i]-d[i]));
	}
	s.clear();
	ll maxi, mini;
	for (i=0;i<key*2;i++) tree[i] = mM;
	for (i=n-1;i>=0;i--) {
		int idx = max((int)(lower_bound(ps,ps+n,max(a.first-ps[i],b.first+ps[i]))-ps),i+1);
		int jdx = upper_bound(ps,ps+n,min(a.second-ps[i],b.second+ps[i]))-ps;
		if (idx<=jdx) return true;
	}
	return false;
}

bool cmp(int a, int b) {return ps[a]+d[a]<ps[b]+d[b];}
ll find_shortcut(int N, vector<int> l, vector<int> dt, int C) {
	int i;
	n=N; c=C;
	ps[0] = 0;
	for (i=1;i<n;i++) ps[i] += ps[i-1]+l[i-1];
	for (i=0;i<n;i++) d[i] = dt[i];
	for (i=0;i<n;i++) pspd[i] = ps[i]+d[i];
	for (i=0;i<n;i++) ord[i] = i;
	sort(pspd,pspd+n);
	sort(ord,ord+n,cmp);
	for (i=0;i<n;i++) rord[ord[i]] = i;
	ll s = 0, e = 1LL<<51;
	while(s<=e) {
		ll m = (s+e)>>1;
		if (ok(m)) e = m-1;
		else s = m+1;
	}
    return s;
}

Compilation message

shortcut.cpp: In function 'bool ok(ll)':
shortcut.cpp:56:5: warning: unused variable 'maxi' [-Wunused-variable]
  ll maxi, mini;
     ^
shortcut.cpp:56:11: warning: unused variable 'mini' [-Wunused-variable]
  ll maxi, mini;
           ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 73816 KB n = 4, 80 is a correct answer
2 Correct 589 ms 73816 KB n = 9, 110 is a correct answer
3 Correct 553 ms 73816 KB n = 4, 21 is a correct answer
4 Correct 533 ms 73816 KB n = 3, 4 is a correct answer
5 Correct 623 ms 73816 KB n = 2, 62 is a correct answer
6 Correct 609 ms 73816 KB n = 2, 3 is a correct answer
7 Correct 609 ms 73816 KB n = 3, 29 is a correct answer
8 Correct 619 ms 73816 KB n = 2, 3 is a correct answer
9 Correct 613 ms 73816 KB n = 2, 3 is a correct answer
10 Correct 636 ms 73816 KB n = 2, 2000000001 is a correct answer
11 Correct 599 ms 73816 KB n = 2, 3000000000 is a correct answer
12 Correct 613 ms 73816 KB n = 3, 3000000000 is a correct answer
13 Correct 606 ms 73816 KB n = 3, 3000000000 is a correct answer
14 Correct 599 ms 73816 KB n = 4, 3000000001 is a correct answer
15 Correct 593 ms 73816 KB n = 4, 4000000000 is a correct answer
16 Correct 606 ms 73816 KB n = 5, 4000000000 is a correct answer
17 Correct 596 ms 73816 KB n = 10, 1000000343 is a correct answer
18 Incorrect 589 ms 73816 KB n = 10, incorrect answer: jury 3189 vs contestant 3040
19 Halted 0 ms 0 KB -