oj.uz

Submission #875035

# Submission time Handle Problem Language Result Execution time Memory
875035 2023-11-18T14:23:36 Z garam1732 Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 35104 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];

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

map<pi, ll> mp1, mp2;

void dijkstra(int s, map<pi, ll>& mp) {
    mp[pi(s, 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] != 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));
            if(!mp.count(there) || mp[there] > cost+x.ss.ff) {
                mp[there] = cost+x.ss.ff;
                pq.push(pii(-mp[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();

        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);
        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:32:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = s+e>>1;
      |               ~^~
pinball.cpp: In function 'void update(int, int, int, int, int, int)':
pinball.cpp:44:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = s+e>>1;
      |               ~^~

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26984 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 6 ms 27144 KB Output is correct
8 Correct 5 ms 26968 KB Output is correct
9 Correct 9 ms 27228 KB Output is correct
10 Correct 8 ms 27256 KB Output is correct
11 Correct 7 ms 27228 KB Output is correct
12 Correct 7 ms 27240 KB Output is correct
13 Correct 7 ms 27228 KB Output is correct
14 Correct 6 ms 27276 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26984 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 6 ms 27144 KB Output is correct
8 Correct 5 ms 26968 KB Output is correct
9 Correct 9 ms 27228 KB Output is correct
10 Correct 8 ms 27256 KB Output is correct
11 Correct 7 ms 27228 KB Output is correct
12 Correct 7 ms 27240 KB Output is correct
13 Correct 7 ms 27228 KB Output is correct
14 Correct 6 ms 27276 KB Output is correct
15 Correct 7 ms 27228 KB Output is correct
16 Correct 7 ms 27228 KB Output is correct
17 Correct 46 ms 28432 KB Output is correct
18 Correct 60 ms 28756 KB Output is correct
19 Correct 29 ms 27992 KB Output is correct
20 Correct 50 ms 28752 KB Output is correct
21 Correct 7 ms 27228 KB Output is correct
22 Correct 10 ms 27604 KB Output is correct
23 Correct 10 ms 27736 KB Output is correct
24 Correct 11 ms 27484 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 5 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 6 ms 26984 KB Output is correct
6 Correct 6 ms 26972 KB Output is correct
7 Correct 6 ms 27144 KB Output is correct
8 Correct 5 ms 26968 KB Output is correct
9 Correct 9 ms 27228 KB Output is correct
10 Correct 8 ms 27256 KB Output is correct
11 Correct 7 ms 27228 KB Output is correct
12 Correct 7 ms 27240 KB Output is correct
13 Correct 7 ms 27228 KB Output is correct
14 Correct 6 ms 27276 KB Output is correct
15 Correct 7 ms 27228 KB Output is correct
16 Correct 7 ms 27228 KB Output is correct
17 Correct 46 ms 28432 KB Output is correct
18 Correct 60 ms 28756 KB Output is correct
19 Correct 29 ms 27992 KB Output is correct
20 Correct 50 ms 28752 KB Output is correct
21 Correct 7 ms 27228 KB Output is correct
22 Correct 10 ms 27604 KB Output is correct
23 Correct 10 ms 27736 KB Output is correct
24 Correct 11 ms 27484 KB Output is correct
25 Execution timed out 1050 ms 35104 KB Time limit exceeded
26 Halted 0 ms 0 KB -