Submission #875043

#	Time	Username	Problem	Language	Result	Execution time	Memory
875043		garam1732	Pinball (JOI14_pinball)	C++14	51 / 100	1046 ms	516232 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<int, 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<int> ls[1<<20];
int cnt;

vector<pi> adj[1<<20];
int num[1<<20], idx[1<<20];

void init(int node, int s, int e) {
    //v.push_back(pi(node, 0));
    ls[node].push_back(cnt++);

    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[ls[node<<1][0]].push_back(pi(ls[node][0], 0)); adj[ls[node<<1|1][0]].push_back(pi(ls[node][0], 0));
}

void update(int node, int s, int e, int l, int r, pi v) {
    if(e < l || r < s) return;
    if(l <= s && e <= r) {
        for(int x : ls[node]) adj[x].push_back(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);
}

vector<ll> d1, d2;

void dijkstra(int s, vector<ll>& d) {
    d.resize(cnt, LLONG_MAX); d[s] = 0;
    priority_queue<pll> pq; pq.push(pll(0, s));
    while(pq.size()) {
        int here = pq.top().ss; ll cost = -pq.top().ff; pq.pop();
       // cout<<'a'<<here.ff<<bl<<here.ss<<bl<<cost<<endl;

        if(d[here] != cost) continue;

        for(auto [there, w] : adj[here]) {
            if(d[there] > cost+w) {
                d[there] = cost+w;
                pq.push(pll(-d[there], there));
            }
        }
    }
}

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();
    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();

        idx[i] = cnt;
        ls[num[wall[i].c]].push_back(cnt);
        update(1, 0, sz-1, wall[i].a, wall[i].b, pi(cnt++, wall[i].d));
        int x = num[wall[i].c]>>1;
        while(x) {
            adj[cnt-1].push_back(pi(cnt, 0));
            ls[x].push_back(cnt++);
            x >>= 1;
        }
    }

    dijkstra(ls[num[0]][0], d1); dijkstra(ls[num[sz-1]][0], d2);

//    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++) {
        int x = idx[i];
        if(d1[x] < LLONG_MAX && d2[x] < LLONG_MAX)
            ans = min(ans, d1[x]+d2[x]-wall[i].d);

        if(wall[i].c == 0 && d2[x] < LLONG_MAX) ans = min(ans, d2[x]);
        if(wall[i].c == sz-1 && d1[x] < LLONG_MAX) ans = min(ans, d1[x]);
    }

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

Compilation message (stderr)

pinball.cpp: In function 'void init(int, int, int)':
pinball.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = s+e>>1;
      |               ~^~
pinball.cpp: In function 'void update(int, int, int, int, int, pi)':
pinball.cpp:51:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = s+e>>1;
      |               ~^~
pinball.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
pinball.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [there, w] : adj[here]) {
      |                  ^

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