Submission #76971

#	Time	Username	Problem	Language	Result	Execution time	Memory
76971		Vardanyan	Pinball (JOI14_pinball)	C++14	100 / 100	878 ms	137220 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
const int N = 1000*100+5;
const long long INF = 10000000000000005;
int A[N],B[N],C[N];
long long D[N];
long long dp1[N];
long long dp2[N];
struct node{
    node* l;
    node* r;
    long long val;
    node():l(NULL),r(NULL),val(INF){}
};
void update(node* v,int s,int e,int l,int r,long long val){
    if(l>r) return;
    if(s == l && e == r){
        v->val = val;
        return;
    }
    int m = (s+e)/2;
    if(v->l == NULL){
        v->l = new node();
        v->r = new node();
    }
    update(v->l,s,m,l,min(m,r),val);
    update(v->r,m+1,e,max(l,m+1),r,val);
    v->val = min(v->l->val,v->r->val);
}
long long query(node* v,int s,int e,int l,int r){
    if(l>r || v == NULL) return INF;
    if(s == l && e == r) return v->val;
    int m = (s+e)/2;
    return min(query(v->l,s,m,l,min(m,r)),query(v->r,m+1,e,max(l,m+1),r));
}
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    node* l = new node();
    node* r = new node();
    long long ans = INF;
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d%lld",&A[i],&B[i],&C[i],&D[i]);
        long long cl;
        if(A[i] == 1){
            cl = D[i];
        }
        else{
            cl = query(l,1,n,A[i],B[i]);
            cl+=D[i];
        }
        long long x = query(l,1,n,C[i],C[i]);
        if(x>cl){
            update(l,1,n,C[i],C[i],cl);
        }
        long long cr;
        if(B[i] == n){
            cr = D[i];
        }
        else{
            cr = query(r,1,n,A[i],B[i]);
            cr+=D[i];
        }
        x = query(r,1,n,C[i],C[i]);
        if(x>cr){
            update(r,1,n,C[i],C[i],cr);
        }
        ans = min(ans,cl+cr-D[i]);
    }
    if(ans == INF) ans = -1;
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&m,&n);
     ~~~~~^~~~~~~~~~~~~~
pinball.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%lld",&A[i],&B[i],&C[i],&D[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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