oj.uz

Submission #240552

# Submission time Handle Problem Language Result Execution time Memory
240552 2020-06-19T23:20:05 Z aggu_01000101 Pinball (JOI14_pinball) C++14
100 / 100
 245 ms 12404 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 100000000000000000
#define int long long
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
struct RR{
    int left, right, hole, cost;
};
const int M = (int)1e5 + 5;
int m, n;
int ans = INF;
int dp1[M], dp2[M];
int seg[4*M][2]; //left -> 0, right -> 1
RR arr[M];
void build(int l, int u, int i){
    seg[i][0] = seg[i][1] = INF;
    if(l==u) return;
    build(l, mid(l, u), lchild(i));
    build(mid(l, u)+1, u, rchild(i));
}
int query(int l, int u, int i, int ll, int uu, int tt){
    if(l>=ll && u<=uu) return seg[i][tt];
    if(l>uu || u<ll) return INF;
    return min(query(l, mid(l, u), lchild(i), ll, uu, tt), query(mid(l, u)+1, u, rchild(i), ll, uu, tt));
}
int update(int l, int u, int i, int ll, int up, int tt){
    if(l>=ll && u<=ll) return seg[i][tt] = min(up, seg[i][tt]);
    if(l>ll || u<ll) return seg[i][tt];
    return seg[i][tt] = min(update(l, mid(l, u), lchild(i), ll, up, tt), update(mid(l,u)+1, u, rchild(i), ll, up, tt));
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //2 3 3 4 5
    cin>>m>>n;
    vector<int> holes;
    for(int i = 0;i<m;i++){
        cin>>arr[i].left>>arr[i].right>>arr[i].hole>>arr[i].cost;
        holes.push_back(arr[i].hole);
    }
    build(0, m-1, 0);
    sort(holes.begin(), holes.end());
    for(int i = 0;i<m;i++){
        int begc = lower_bound(holes.begin(), holes.end(), arr[i].left) - holes.begin(); //index of first hole that is in the range
        int endc = (upper_bound(holes.begin(), holes.end(), arr[i].right) - holes.begin()) - 1; //index of last hole that is in the range
        int currc = lower_bound(holes.begin(), holes.end(), arr[i].hole) - holes.begin();
        //cout<<begc<<" "<<endc<<" "<<arr[i].left<<" "<<arr[i].right<<"\n";
        //Getting it here from the right
        int rightcost = (arr[i].right == n)?0:query(0, m-1, 0, begc, endc, 1);
        int leftcost = (arr[i].left==1)?0:query(0, m-1, 0, begc, endc, 0);
        //cout<<i<<" "<<leftcost<<" "<<rightcost<<" "<<arr[i].cost<<"\n";
        //calculate cost of using this as the funnel
        ans = min(ans, leftcost + rightcost + arr[i].cost);
        //update cost of going through this hole
        //right
        update(0, m-1, 0, currc, rightcost + arr[i].cost, 1);
        //left
        update(0, m-1, 0, currc, leftcost + arr[i].cost, 0);
    }
    if(ans>=INF) ans = -1;
    cout<<ans<<"\n";
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 312 KB Output is correct
14 Correct 6 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 312 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 7 ms 512 KB Output is correct
20 Correct 6 ms 512 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 ms 512 KB Output is correct
23 Correct 6 ms 512 KB Output is correct
24 Correct 7 ms 512 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 312 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 512 KB Output is correct
19 Correct 7 ms 512 KB Output is correct
20 Correct 6 ms 512 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 ms 512 KB Output is correct
23 Correct 6 ms 512 KB Output is correct
24 Correct 7 ms 512 KB Output is correct
25 Correct 23 ms 1664 KB Output is correct
26 Correct 54 ms 3456 KB Output is correct
27 Correct 161 ms 10104 KB Output is correct
28 Correct 226 ms 12404 KB Output is correct
29 Correct 107 ms 6388 KB Output is correct
30 Correct 236 ms 12396 KB Output is correct
31 Correct 245 ms 12400 KB Output is correct
32 Correct 233 ms 12400 KB Output is correct
33 Correct 36 ms 2944 KB Output is correct
34 Correct 104 ms 6388 KB Output is correct
35 Correct 170 ms 12400 KB Output is correct
36 Correct 231 ms 12400 KB Output is correct
37 Correct 205 ms 12400 KB Output is correct
38 Correct 205 ms 12396 KB Output is correct