Submission #1020591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020591		1L1YA	Pinball (JOI14_pinball)	C++17	100 / 100	191 ms	29124 KiB

pinball

//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e16;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=3e5+11;
const int lg=23;

ll n,m,T,a[N],b[N],c[N],d[N],dpl[N],dpr[N],seg[2][N<<2];
vector<int> comp;

void modify(int ind,int pos,ll val,int id=1,int l=0,int r=T){
	if(r-l==1){
		seg[ind][id]=min(seg[ind][id],val);
		return;
	}
	if(pos<mid)	modify(ind,pos,val,lc,l,mid);
	else	modify(ind,pos,val,rc,mid,r);
	seg[ind][id]=min(seg[ind][lc],seg[ind][rc]);
}

ll get(int ind,int ql,int qr,int id=1,int l=0,int r=T){
	if(qr<=l || ql>=r)	return oo;
	if(ql<=l && r<=qr)	return seg[ind][id];
	return min(get(ind,ql,qr,lc,l,mid),get(ind,ql,qr,rc,mid,r));
}

int main(){
	FastIO

	cin >> n >> m;
	comp.Pb(1);comp.Pb(m+1);
	for(int i=1;i<=n;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		b[i]++;
		comp.Pb(a[i]);
		comp.Pb(b[i]);
		comp.Pb(c[i]);
	}
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(all(comp),a[i])-comp.begin();
		b[i]=lower_bound(all(comp),b[i])-comp.begin();
		c[i]=lower_bound(all(comp),c[i])-comp.begin();
	}
	T=SZ(comp);
	fill(seg[0],seg[0]+(T<<2),oo);
	fill(seg[1],seg[1]+(T<<2),oo);
	ll ans=oo;
	for(int i=1;i<=n;i++){
		dpl[i]=dpr[i]=oo;
		if(!a[i])	dpl[i]=d[i];
		if(b[i]==T-1)	dpr[i]=d[i];
		dpl[i]=min(dpl[i],get(0,a[i],b[i])+d[i]);
		dpr[i]=min(dpr[i],get(1,a[i],b[i])+d[i]);
		ans=min(ans,dpl[i]+dpr[i]-d[i]);
		modify(0,c[i],dpl[i]);
		modify(1,c[i],dpr[i]);
	}
	cout << (ans==oo?-1:ans) << endl;

	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void modify(int, int, ll, int, int, int)':
pinball.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
pinball.cpp:45:9: note: in expansion of macro 'mid'
   45 |  if(pos<mid) modify(ind,pos,val,lc,l,mid);
      |         ^~~
pinball.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
pinball.cpp:45:38: note: in expansion of macro 'mid'
   45 |  if(pos<mid) modify(ind,pos,val,lc,l,mid);
      |                                      ^~~
pinball.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
pinball.cpp:46:29: note: in expansion of macro 'mid'
   46 |  else modify(ind,pos,val,rc,mid,r);
      |                             ^~~
pinball.cpp: In function 'll get(int, int, int, int, int, int)':
pinball.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
pinball.cpp:53:32: note: in expansion of macro 'mid'
   53 |  return min(get(ind,ql,qr,lc,l,mid),get(ind,ql,qr,rc,mid,r));
      |                                ^~~
pinball.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
pinball.cpp:53:54: note: in expansion of macro 'mid'
   53 |  return min(get(ind,ql,qr,lc,l,mid),get(ind,ql,qr,rc,mid,r));
      |                                                      ^~~

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