Submission #29136

#	Time	Username	Problem	Language	Result	Execution time	Memory
29136		osmanorhan	Pinball (JOI14_pinball)	C++14	100 / 100	199 ms	9124 KiB

pinball

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

inline int read() {
    int res = 0 ;int neg ;
    while(true){char ch = getchar();if(ch>='0' && ch<='9' || ch=='-'){if(ch=='-') neg = -1;else neg = 1 , res = ch-'0';break;} }
    while(true){char ch = getchar();if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';else break;}
    return res*neg;
}


typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<db,db> dd;
typedef pair<db,int> di;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;

const int maxn = 100020;
const int maxm = 1000020;
const int MOd = 1e9 + 7;

Lint segment[maxn*3][2];
int n, a, b;
int l[maxn], r[maxn], c[maxn], ar[maxn];
vector<int> v;

void up( int x, Lint t, int tp ) {
    umin( segment[x+n-1][tp], t );
    for(int k=(x+n-1)>>1;k;k>>=1) segment[k][tp] = min( segment[k+k][tp], segment[k+k+1][tp] );
}

Lint find( int l, int r, int tp ) {
    Lint ret = 1e18;
    for( l+=n-1, r+=n-1; l <= r; l=(l+1)>>1, r = (r-1)>>1 ) {
        if( l&1 ) umin( ret, segment[l][tp] );
        if( ~r&1 ) umin( ret, segment[r][tp] );
    }
    return ret;
}

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("out.txt","w",stdout);

    scanf("%d %d",&a,&b);
    v.pb( 1 );
    v.pb( b );
    for(int i=1;i<=a;i++) {
        scanf("%d %d %d %d",&l[i],&r[i],&c[i],&ar[i]);
        v.pb( c[i] );
    }
    sort( all( v ) );
    v.erase( unique( all( v ) ), v.end() );

    n = 1;
    while( n < v.size() ) n <<= 1;

    for(int i=1;i<n+n;i++) segment[i][0] = segment[i][1] = 1e18;
    up( 1, 0, 0 );
    up( v.size(), 0, 1 );
    //printf("asd %lld %lld -- %d\n",find(1,6,0),find(1,6,1),v.size());
    //for(int i=0;i<v.size();i++) printf("asd %d %d\n",v[i],n);
    Lint ans = 1e18;

    for(int i=1;i<=a;i++) {
        int o = lower_bound( all( v ), c[i] ) - v.begin() + 1;
        int j = lower_bound( all( v ), l[i] ) - v.begin() + 1;
        int k = upper_bound( all( v ), r[i] ) - v.begin();
        Lint ll = find( j, k, 0 );
        Lint rr = find( j, k, 1 );
        //printf("%d %d %d %lld %lld\n",j,k,o,ll,rr);
        up( o, ll+ar[i], 0 );
        up( o, rr+ar[i], 1 );
        umin( ans, ll+rr+ar[i] );
    }
    if( ans >= 1e18 ) ans = -1;
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int read()':
pinball.cpp:31:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     while(true){char ch = getchar();if(ch>='0' && ch<='9' || ch=='-'){if(ch=='-') neg = -1;else neg = 1 , res = ch-'0';break;} }
                                                ^
pinball.cpp: In function 'int main()':
pinball.cpp:84:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while( n < v.size() ) n <<= 1;
              ^
pinball.cpp:73:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);
                         ^
pinball.cpp:77:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&l[i],&r[i],&c[i],&ar[i]);
                                                      ^

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