Submission #401782

#	Time	Username	Problem	Language	Result	Execution time	Memory
401782		lukameladze	Pinball (JOI14_pinball)	C++14	100 / 100	539 ms	34692 KiB

pinball

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
int n,m,cnt;
long long dp[N],dp1[N],a[N],b[N],c[N],d[N],ans;
long long tree[4*N];
map <int, int> xx;
vector <long long> v;
void update(long long  node, long long  le, long long  ri ,long long  idx, long long  val) {
     if (le>idx || ri<idx) return; 
     if (le==ri) {
          tree[node]=min(tree[node],val);
          return ;
     }
     int mid=(le+ri)/2;
     update(2*node, le ,mid, idx, val);
     update(2*node+1, mid+1, ri, idx, val);
     tree[node]=min(tree[2*node],tree[2*node+1]);
}
long long  getans(long long  node, long long  le, long long  ri ,long long  start, long long  end) {
     if (le>end || ri<start) return 1e17; 
     if (le>=start && ri<=end) {
          return tree[node];
     }
     int mid=(le+ri)/2;
     return min(getans(2*node, le ,mid, start, end),getans(2*node+1, mid+1, ri, start,end));
}
int main() {
  std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	v.pb(1);
	
     cin>>m>>n;
    v.pb(n);
	 for (int i=1; i<=m; i++) {
          cin>>a[i]>>b[i]>>c[i]>>d[i];
          v.pb(a[i]);
          v.pb(b[i]);
          v.pb(c[i]);
 	}
 	sort(v.begin(), v.end());
 	xx[v[0]]=1;
 	cnt=1;
 	for (int i=1; i<v.size(); i++) {
 		if (v[i]!=v[i-1]) {
 			cnt++;
 			xx[v[i]]=cnt;
		 }
	 }
	 for (int i=1; i<=m; i++){ 
	 
	 	a[i]=xx[a[i]];
	 	b[i]=xx[b[i]];
	 	c[i]=xx[c[i]];//cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
	 }
	 n=cnt;
     for (int i=1; i<=4*n; i++) {
          tree[i]=1e17;
     }
     for (int i=1; i<=m; i++) {
          if (a[i]==1) {
               dp[i]=d[i];
               update(1,1,n,c[i],dp[i]);
               continue;
          } 
          dp[i]=getans(1,1,n,a[i],b[i])+d[i];
          update(1,1,n,c[i],dp[i]);         
 
     }
     for (int i=1; i<=4*n; i++) {
          tree[i]=1e17;
     }
     for (int i=1; i<=m; i++) {
          if (b[i]==n) {
               dp1[i]=d[i];
               update(1,1,n,c[i],dp1[i]);
               continue;
          }
          dp1[i]=getans(1,1,n,a[i],b[i])+d[i]; 
          update(1,1,n,c[i],dp1[i]);
     }
	 ans=1e17;
     for (int i=1; i<=m; i++) {
	      ans=min(ans, dp[i]+dp1[i]-d[i]);
     }
     if (ans==1e17) cout<<-1;else
     cout<<ans;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int i=1; i<v.size(); i++) {
      |                 ~^~~~~~~~~

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