Submission #287474

#	Time	Username	Problem	Language	Result	Execution time	Memory
287474		Namnamseo	Pinball (JOI14_pinball)	C++17	100 / 100	274 ms	23368 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, w;

const ll inf = 1ll<<60;
struct seg {
	static const int M=524288;
	ll tree[M<<1];
	void init(){ for(ll& x:tree) x=inf; }
	ll rmin(int l, int r){
		l+=M; r+=M; ll ret=inf;
		while(l<=r){
			if(l%2==1) ret=min(ret, tree[l++]);
			if(r%2==0) ret=min(ret, tree[r--]);
			l>>=1; r>>=1;
		}
		return ret;
	}
	void put(int p, ll val){ for(p+=M;p;p>>=1) tree[p]=min(tree[p], val); }
} lt, rt;

typedef tuple<int,int,int,int> t4;
t4 d[100010];

int C[300010], Cn;
int f(int x){ return lower_bound(C, C+Cn, x)-C; }

int main()
{
	read(n, w);
	for(int i=1; i<=n; ++i){
		int a,b,c,d; read(a,b,c,d); ::d[i]=t4{a,b,c,d};
		C[Cn++]=a; C[Cn++]=b; C[Cn++]=c;
	}
	C[Cn++]=1; C[Cn++]=w;
	sort(C, C+Cn); Cn=unique(C, C+Cn)-C;
	lt.init(); rt.init(); lt.put(f(1), 0); rt.put(f(w), 0);
	ll ans=inf;
	for(int i=1; i<=n; ++i){
		int a,b,c,d; tie(a,b,c,d)=::d[i];
		a=f(a); b=f(b); c=f(c);
		ans=min(ans, lt.rmin(a, b) + rt.rmin(a, b) + d);
		lt.put(c, lt.rmin(a, b) + d);
		rt.put(c, rt.rmin(a, b) + d);
	}
	if(ans==inf)ans=-1;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void read(int&)':
pinball.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
pinball.cpp: In function 'void read(ll&)':
pinball.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49