Submission #24505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24505	2017-06-09T14:10:10 Z	Jeyeon Si(#1042)	Shortcut (IOI16_shortcut)	C++	Compilation error	0 ms	0 KB

shortcut

#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(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:59:77: error: no matching function for call to 'max(long int, int)'
   int idx = max(lower_bound(ps,ps+n,max(a.first-ps[i],b.first+ps[i]))-ps,i+1);
                                                                             ^
In file included from /usr/include/c++/5/vector:60:0,
                 from shortcut.h:2,
                 from shortcut.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/5/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
shortcut.cpp:59:77: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   int idx = max(lower_bound(ps,ps+n,max(a.first-ps[i],b.first+ps[i]))-ps,i+1);
                                                                             ^
In file included from /usr/include/c++/5/vector:60:0,
                 from shortcut.h:2,
                 from shortcut.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/5/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
shortcut.cpp:59:77: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   int idx = max(lower_bound(ps,ps+n,max(a.first-ps[i],b.first+ps[i]))-ps,i+1);
                                                                             ^
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;
           ^