oj.uz

Submission #29136

# Submission time Handle Problem Language Result Execution time Memory
29136 2017-07-18T11:12:31 Z osmanorhan Pinball (JOI14_pinball) C++14
100 / 100
 199 ms 9124 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8272 KB Output is correct
2 Correct 0 ms 8272 KB Output is correct
3 Correct 0 ms 8272 KB Output is correct
4 Correct 0 ms 8272 KB Output is correct
5 Correct 0 ms 8272 KB Output is correct
6 Correct 0 ms 8272 KB Output is correct
7 Correct 0 ms 8272 KB Output is correct
8 Correct 0 ms 8272 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8272 KB Output is correct
2 Correct 0 ms 8272 KB Output is correct
3 Correct 0 ms 8272 KB Output is correct
4 Correct 0 ms 8272 KB Output is correct
5 Correct 0 ms 8272 KB Output is correct
6 Correct 0 ms 8272 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8272 KB Output is correct
2 Correct 0 ms 8272 KB Output is correct
3 Correct 0 ms 8272 KB Output is correct
4 Correct 0 ms 8272 KB Output is correct
5 Correct 0 ms 8272 KB Output is correct
6 Correct 0 ms 8272 KB Output is correct
7 Correct 0 ms 8272 KB Output is correct
8 Correct 0 ms 8272 KB Output is correct
9 Correct 0 ms 8272 KB Output is correct
10 Correct 0 ms 8272 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8412 KB Output is correct
2 Correct 33 ms 8544 KB Output is correct
3 Correct 119 ms 9124 KB Output is correct
4 Correct 119 ms 9124 KB Output is correct
5 Correct 83 ms 8740 KB Output is correct
6 Correct 139 ms 9124 KB Output is correct
7 Correct 173 ms 9124 KB Output is correct
8 Correct 179 ms 9124 KB Output is correct
9 Correct 19 ms 8544 KB Output is correct
10 Correct 79 ms 8740 KB Output is correct
11 Correct 99 ms 9124 KB Output is correct
12 Correct 199 ms 9124 KB Output is correct
13 Correct 149 ms 9124 KB Output is correct
14 Correct 139 ms 9124 KB Output is correct