Submission #875073

#	Time	Username	Problem	Language	Result	Execution time	Memory
875073		garam1732	Pinball (JOI14_pinball)	C++14	51 / 100	1063 ms	40000 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<pii> adj[1<<20];
int num[1<<20];
ll t;

void init(int node, int s, int e) {
    if(s == e) {
        num[s] = node;
        return;
    }

    int mid = s+e>>1;
    init(node<<1, s, mid); init(node<<1|1, mid+1, e);
    adj[node<<1].push_back(pii(node, pi(0, 0))); adj[node<<1|1].push_back(pii(node, pi(0, 0)));
}

void update(int node, int s, int e, int l, int r, int v) {
    if(e < l || r < s) return;
    if(l <= s && e <= r) {
        adj[node].push_back(pii(num[wall[v].c], pi(wall[v].d, v)));
        return;
    }

    int mid = s+e>>1;
    update(node<<1, s, mid, l, r, v); update(node<<1|1, mid+1, e, l, r, v);
}

unordered_map<ll, ll> mp1, mp2;

void dijkstra(int s, unordered_map<ll, ll>& mp) {
    mp[s*t+0] = 0;
    priority_queue<pii> pq; pq.push(pii(0, pi(s, 0)));
    while(pq.size()) {
        pi here = pq.top().ss; ll cost = -pq.top().ff; pq.pop();
       // cout<<'a'<<here.ff<<bl<<here.ss<<bl<<cost<<endl;

        if(mp[here.ff*t+here.ss] != cost) continue;

        for(auto x : adj[here.ff]) {
            if(x.ss.ss && x.ss.ss <= here.ss) continue;

            //pi there = pi(x.ff, max(x.ss.ss, here.ss));
            ll there = x.ff*t+max(x.ss.ss, here.ss);

            if(!mp.count(there) || mp[there] > cost+x.ss.ff) {
                mp[there] = cost+x.ss.ff;
                pq.push(pii(-mp[there], pi(x.ff, max(x.ss.ss, here.ss))));
            }
        }
    }
}

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

    int m, n; cin >> m >> n; t = m+1;
    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();
    init(1, 0, sz-1);
    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();

        update(1, 0, sz-1, wall[i].a, wall[i].b, i);
    }

    dijkstra(num[0], mp1); dijkstra(num[sz-1], mp2);

//    for(auto x : mp1) {
//        cout<<x.ff.ff<<bl<<x.ff.ss<<bl<<x.ss<<endl;
//    }

    ll ans = LLONG_MAX;
    for(int i = 1; i <= m; i++) {
        //pi v = pi(num[wall[i].c], i);
        ll v = num[wall[i].c]*t+i;
        if(mp1.count(v) && mp2.count(v))
            ans = min(ans, mp1[v]+mp2[v]-wall[i].d);

        if(wall[i].c == 0 && mp2.count(v)) ans = min(ans, mp2[v]);
        if(wall[i].c == sz-1 && mp1.count(v)) ans = min(ans, mp1[v]);
    }

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

Compilation message (stderr)

pinball.cpp: In function 'void init(int, int, int)':
pinball.cpp:33:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = s+e>>1;
      |               ~^~
pinball.cpp: In function 'void update(int, int, int, int, int, int)':
pinball.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = s+e>>1;
      |               ~^~

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