oj.uz

Submission #401772

# Submission time Handle Problem Language Result Execution time Memory
401772 2021-05-10T19:46:51 Z lukameladze Pinball (JOI14_pinball) C++14
11 / 100
 1000 ms 247028 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long dp[N],dp1[N],n,m,a[N],b[N],c[N],d[N],ans;
map <long long,long long> tree;
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() {
     cin>>m>>n;
     for (int i=1; i<=m; i++) {
          cin>>a[i]>>b[i]>>c[i]>>d[i];
     }
     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]);          //cout<<dp[5]<<endl;
 
     }
     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++) {
     //	cout<<dp[i]<<" "<<dp1[i]<<" "<<dp1[i]-d[i]<<" "<<d[i]<<" "<<dp[i]+dp1[i]-d[i]<<endl;
	      ans=min(ans, dp[i]+dp1[i]-d[i]);
     }
     if (ans==1e17) cout<<-1<<endl;else
     cout<<ans<<endl;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Execution timed out 1095 ms 247028 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Execution timed out 1095 ms 247028 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 428 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Execution timed out 1095 ms 247028 KB Time limit exceeded
10 Halted 0 ms 0 KB -