oj.uz

Submission #947645

# Submission time Handle Problem Language Result Execution time Memory
947645 2024-03-16T17:31:18 Z ND0322 Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 3420 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>

using namespace std;

const int MAXN = 1e5+5;

int n, m;

long long st[MAXN][2];

vector<int> coord;

pair<pair<int,int>,pair<int,int>> a[MAXN];

//n^2
//for some filter have dpl representing path to 0 and dpr representing path to 1
//we look for some thing within this range we jump from
//update dp state as the position of the out part of the filter

//full just throw a sparse seg tree over that sh
//nvm sparse dont work coord compress

void update(int node, int l, int r, int i, long long x, bool t){
    if(l == r){
        st[node][t] = min(st[node][t], x);
        return;
    }

    int mid = (l+r)>>1;
    if(i <= mid) update(node<<1,l,mid,i,x,t);
    else update(node<<1|1, mid+1,r,i,x,t);
    

    st[node][t] = min(st[node<<1][t], st[node<<1|1][t]);
}

long long query(int node, int l, int r, int x, int y, bool t){
    if(x > r || y < l) return 1e18;
    if(x <= l && y >= r) return st[node][t];
    int mid = (l+r)>>1;
    return min(query(node<<1, l,mid, x, y, t), query(node<<1|1, mid+1,r,x,y,t));
}

int get(int x){
    return (int)(lower_bound(coord.begin(), coord.end(), x) - coord.begin())+1;
}

int main(){
    cin >> n >> m;

    coord.push_back(1);
    coord.push_back(m);

    for(int i = 1; i <= n; i++){
        cin >> a[i].first.first >> a[i].first.second >> a[i].second.first >> a[i].second.second;

        coord.push_back(a[i].first.first);
        coord.push_back(a[i].first.second);
        coord.push_back(a[i].second.first);
    }

    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());

    memset(st, 0x3f, sizeof(st));

    m = coord.size();

    update(1,1,m,get(1), 0, 0);
    update(1,1,m,get(m),0,1);

    //cout << query(1,1,m, 1, 3, 0) << "\n";

  

    long long ans = 1e18;

    for(int i = 1; i <= n; i++){
        auto [l,r] = a[i].first;

        l = get(l);
        r = get(r);

        

        long long x = query(1,1,m,l,r,0) + a[i].second.second;
        long long y = query(1,1,m,l,r,1) + a[i].second.second;

        //cout << l << " " << r << " " << x << " " << y << "\n";


        ans = min(ans, x + y - a[i].second.second);
        update(1,1,m,get(a[i].second.first), x, 0);
        update(1,1,m,get(a[i].second.first), y, 1);
    }

    cout << (ans >= 1e18 ? -1 : ans) << "\n";
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -