oj.uz

Submission #875073

# Submission time Handle Problem Language Result Execution time Memory
875073 2023-11-18T15:36:21 Z garam1732 Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 40000 KB 
#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

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

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 5 ms 27144 KB Output is correct
7 Correct 5 ms 26968 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7 ms 27200 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27108 KB Output is correct
13 Correct 6 ms 27224 KB Output is correct
14 Correct 7 ms 27324 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 5 ms 27144 KB Output is correct
7 Correct 5 ms 26968 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7 ms 27200 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27108 KB Output is correct
13 Correct 6 ms 27224 KB Output is correct
14 Correct 7 ms 27324 KB Output is correct
15 Correct 6 ms 26968 KB Output is correct
16 Correct 6 ms 27228 KB Output is correct
17 Correct 21 ms 27996 KB Output is correct
18 Correct 21 ms 28456 KB Output is correct
19 Correct 14 ms 27996 KB Output is correct
20 Correct 19 ms 28252 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 7 ms 27484 KB Output is correct
23 Correct 7 ms 27480 KB Output is correct
24 Correct 7 ms 27480 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 26972 KB Output is correct
6 Correct 5 ms 27144 KB Output is correct
7 Correct 5 ms 26968 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7 ms 27200 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27108 KB Output is correct
13 Correct 6 ms 27224 KB Output is correct
14 Correct 7 ms 27324 KB Output is correct
15 Correct 6 ms 26968 KB Output is correct
16 Correct 6 ms 27228 KB Output is correct
17 Correct 21 ms 27996 KB Output is correct
18 Correct 21 ms 28456 KB Output is correct
19 Correct 14 ms 27996 KB Output is correct
20 Correct 19 ms 28252 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 7 ms 27484 KB Output is correct
23 Correct 7 ms 27480 KB Output is correct
24 Correct 7 ms 27480 KB Output is correct
25 Execution timed out 1063 ms 40000 KB Time limit exceeded
26 Halted 0 ms 0 KB -