Submission #1058747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058747		phong	Pinball (JOI14_pinball)	C++17	100 / 100	123 ms	30360 KiB

pinball

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax =  3e5+ 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int m, n;
struct node{
    int a, b, c, d;
}a[nmax];
vector<int> nen;

struct SEG{
    ll tree[nmax << 2];
    void build(int id, int l, int r){
        if(l == r){
            tree[id] = oo;
            return;
        }
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
    }

    void update(int id, int l, int r, int u, ll val){
        if(l > u || r < u) return;
        if(l == r){
            tree[id] = min(tree[id], val);
            return;
        }
        int mid = r + l >> 1;
        update(id << 1, l, mid, u, val);
        update(id << 1 | 1, mid + 1, r, u, val);
        tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v){
        if(l >= u && r <= v) return tree[id];
        int mid = r + l >> 1;
        if(mid < u) return get(id << 1 | 1, mid+ 1, r, u, v);
        if(mid + 1 > v) return get(id << 1 , l, mid, u, v);
        return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
}one, two;
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> m>> n;
    nen.push_back(1);
    for(int i = 1; i <= m; ++i){
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        nen.push_back(a[i].a);
        nen.push_back(a[i].b);
        nen.push_back(a[i].c);
    }
    nen.push_back(n);
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for(int i = 1; i <= m; ++i){
        a[i].a = lower_bound(nen.begin(), nen.end(), a[i].a) - nen.begin() + 1;
        a[i].b = lower_bound(nen.begin(), nen.end(), a[i].b) - nen.begin() + 1;
        a[i].c = lower_bound(nen.begin(), nen.end(), a[i].c) - nen.begin() + 1;
    }
    int sz = nen.size();//#
    one.build(1, 1, sz); two.build(1, 1, sz);
    one.update(1, 1, sz, 1, 0);
    two.update(1, 1, sz, sz, 0);
    ll ans = oo;
    for(int i = 1; i <= m; ++i){
        ll x =one.get(1, 1, sz, a[i].a, a[i].b);
        ll y = two.get(1, 1, sz, a[i].a, a[i].b);
        ans = min(ans, x + y + a[i].d);
        one.update(1, 1, sz, a[i].c, x + a[i].d);
        two.update(1, 1, sz, a[i].c, y + a[i].d);
    }
    if(ans < oo / 2) cout << ans;
    else cout << -1;
}
/*
5 1
38 44
30 46
2 42
6 24
2 5 30 1 13



*/

Compilation message (stderr)

pinball.cpp: In member function 'void SEG::build(long long int, long long int, long long int)':
pinball.cpp:29:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid = r + l >> 1;
      |                   ~~^~~
pinball.cpp: In member function 'void SEG::update(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = r + l >> 1;
      |                   ~~^~~
pinball.cpp: In member function 'long long int SEG::get(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = r + l >> 1;
      |                   ~~^~~
pinball.cpp: At global scope:
pinball.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~

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