oj.uz

Submission #77746

# Submission time Handle Problem Language Result Execution time Memory
77746 2018-09-30T07:18:56 Z nxteru Pinball (JOI14_pinball) C++14
0 / 100
 16 ms 17144 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,m,k,x[100005],y[100005],z[100005],d[100005],seg[2][1<<20],ans=INF;
vector<ll>cm;
map<ll,ll>pr;
void ini(void){
    for(int i=0;i<1<<20;i++){
        seg[0][i]=INF;
        seg[1][i]=INF;
    }
}
void up(int s,int a,ll b){
    a+=(1<<19)-1;
    seg[s][a]=min(seg[s][a],b);
    while(a>0){
        a=(a-1)/2;
        seg[s][a]=min(seg[s][a*2+1],seg[s][a*2+2]);
    }
}
ll que(int s,int a,int b,int l,int r,int o){
    if(r<a||b<l)return INF;
    if(a<=l&&r<=b)return seg[s][o];
    return min(que(s,a,b,l,(l+r-1)/2,o*2+1),que(s,a,b,(l+r+1)/2,r,o*2+2));
}
int main(void){
    scanf("%lld%lld",&n,&m);
    cm.PB(1);
    cm.PB(m);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld%lld",x+i,y+i,z+i,d+i);
        cm.PB(x[i]);
        cm.PB(y[i]);
        cm.PB(z[i]);
    }
    sort(cm.begin(),cm.end());
    cm.erase(unique(cm.begin(),cm.end()),cm.end());
    k=cm.size();
    for(int i=0;i<k;i++)pr[cm[i]]=i;
    for(int i=0;i<n;i++){
        x[i]=pr[x[i]];
        y[i]=pr[y[i]];
        z[i]=pr[z[i]];
    }
    m=pr[m];
    ini();
    up(0,0,0);
    up(1,m,0);
    for(int i=0;i<n;i++){
        ans=min(ans,que(0,x[i],y[i],0,(1<<19)-1,0)+que(1,x[i],y[i],0,(1<<19)-1,0)+d[i]);
        up(0,z[i],que(0,x[i],y[i],0,(1<<19)-1,0)+d[i]);
        up(1,z[i],que(1,x[i],y[i],0,(1<<19)-1,0)+d[i]);
    }
    printf("%lld\n",ans);
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
pinball.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",x+i,y+i,z+i,d+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 15 ms 16888 KB Output is correct
3 Correct 15 ms 16920 KB Output is correct
4 Correct 15 ms 17096 KB Output is correct
5 Correct 15 ms 17096 KB Output is correct
6 Correct 15 ms 17096 KB Output is correct
7 Incorrect 15 ms 17144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 15 ms 16888 KB Output is correct
3 Correct 15 ms 16920 KB Output is correct
4 Correct 15 ms 17096 KB Output is correct
5 Correct 15 ms 17096 KB Output is correct
6 Correct 15 ms 17096 KB Output is correct
7 Incorrect 15 ms 17144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 15 ms 16888 KB Output is correct
3 Correct 15 ms 16920 KB Output is correct
4 Correct 15 ms 17096 KB Output is correct
5 Correct 15 ms 17096 KB Output is correct
6 Correct 15 ms 17096 KB Output is correct
7 Incorrect 15 ms 17144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16760 KB Output is correct
2 Correct 15 ms 16888 KB Output is correct
3 Correct 15 ms 16920 KB Output is correct
4 Correct 15 ms 17096 KB Output is correct
5 Correct 15 ms 17096 KB Output is correct
6 Correct 15 ms 17096 KB Output is correct
7 Incorrect 15 ms 17144 KB Output isn't correct
8 Halted 0 ms 0 KB -