oj.uz

Submission #343465

# Submission time Handle Problem Language Result Execution time Memory
343465 2021-01-04T00:43:50 Z eyangch Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 364 KB 
/*
Solution: O(M logM)
Have two strictly increasing maps to store the required cost for left boundaries and right boundaries.
(Strictly increasing allows retrieval of min cost for a device in O(logN) time)
*/

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct si_map{
    map<int, int> mp;

    void insert(int x, int v){
        auto it = mp.lower_bound(x);
        if(it != mp.end() && it->second <= v){
            return;
        }
        if(it != mp.begin()){
            it--;
            vector<int> rm;
            while(true){
                if(it->second < v){
                    break;
                }
                rm.push_back(it->first);
                if(it == mp.begin()){
                    break;
                }
                it--;
            }
            for(int i : rm){
                mp.erase(i);
            }
        }
        //cout << "INSERT: " << x << " " << v << endl;
        mp[x] = v;
    }

    int qry(int x){
        auto it = mp.lower_bound(x);
        if(it == mp.end()){
            return 1e16;
        }
        return it->second;
    }
};

int M, N;
si_map l, r;

int32_t main(){
    cin >> M >> N;
    int ans = 1e16;
    l.insert(1, 0);
    r.insert(-N, 0);
    for(int i = 0; i < M; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int lcost = l.qry(a), rcost = r.qry(-b);
        ans = min(ans, lcost + rcost + d);
        l.insert(c, lcost + d);
        r.insert(-c, rcost + d); 
    }
    cout << ans << endl;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -