Submission #875536

#	Time	Username	Problem	Language	Result	Execution time	Memory
875536		garam1732	Pinball (JOI14_pinball)	C++14	100 / 100	198 ms	23296 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl " "
#define endl "\n"
#define all(v) v.begin(), v.end()
#define comp(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, pi> pii;
typedef pair<ll, ll> pll;

const int MAXN = 100100;
const int MOD = 1e9+7;

struct Wall {
    int a, b, c, d;
}wall[MAXN];

vector<pi> cp;
vector<ll> tree1, tree2;

void update(vector<ll>& tree, int node, int s, int e, int idx, ll v) {
    if(e < idx || idx < s) return;
    if(s == e) {
        tree[node] = min(tree[node], v);
        return;
    }

    int mid = s+e>>1;
    update(tree, node<<1, s, mid, idx, v); update(tree, node<<1|1, mid+1, e, idx, v);
    tree[node] = min(tree[node<<1], tree[node<<1|1]);
}

ll solve(vector<ll>& tree, int node, int s, int e, int l, int r) {
    if(e < l || r < s) return LLONG_MAX;
    if(l <= s && e <= r) return tree[node];

    int mid = s+e>>1;
    return min(solve(tree, node<<1, s, mid, l, r), solve(tree, node<<1|1, mid+1, e, l, r));
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int m, n; cin >> m >> n;
    for(int i = 1; i <= m; i++) cin >> wall[i].a >> wall[i].b >> wall[i].c >> wall[i].d;

    for(int i = 1; i <= m; i++) cp.push_back(pi(wall[i].c, i));
    cp.push_back(pi(1, 0)); cp.push_back(pi(n, 0));

    sort(all(cp)); comp(cp);

    int sz = cp.size();
    for(int i = 1; i <= m; i++) {
        wall[i].a = lower_bound(all(cp), pi(wall[i].a, 0))-cp.begin();
        wall[i].b = lower_bound(all(cp), pi(wall[i].b+1, 0))-cp.begin()-1;
        wall[i].c = lower_bound(all(cp), pi(wall[i].c, i))-cp.begin();
    }

    tree1.resize(1<<20, LLONG_MAX);
    tree2.resize(1<<20, LLONG_MAX);
    update(tree1, 1, 0, sz-1, 0, 0); update(tree2, 1, 0, sz-1, sz-1, 0);

    for(int i = 1; i <= m; i++) {
        ll x = solve(tree1, 1, 0, sz-1, wall[i].a, wall[i].b);
        if(x < LLONG_MAX) update(tree1, 1, 0, sz-1, wall[i].c, x+wall[i].d);

        x = solve(tree2, 1, 0, sz-1, wall[i].a, wall[i].b);
        if(x < LLONG_MAX) update(tree2, 1, 0, sz-1, wall[i].c, x+wall[i].d);
    }

    ll res = min(solve(tree1, 1, 0, sz-1, sz-1, sz-1), solve(tree2, 1, 0, sz-1, 0, 0));
    for(int i = 1; i <= m; i++) {
        ll x = solve(tree1, 1, 0, sz-1, wall[i].c, wall[i].c), y = solve(tree2, 1, 0, sz-1, wall[i].c, wall[i].c);
        if(x < LLONG_MAX && y < LLONG_MAX) res = min(res, x+y-wall[i].d);
    }

    cout << (res == LLONG_MAX ? -1 : res);
}

Compilation message (stderr)

pinball.cpp: In function 'void update(std::vector<long long int>&, int, int, int, int, ll)':
pinball.cpp:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = s+e>>1;
      |               ~^~
pinball.cpp: In function 'll solve(std::vector<long long int>&, int, int, int, int, int)':
pinball.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = s+e>>1;
      |               ~^~

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