Submission #314269

#	Time	Username	Problem	Language	Result	Execution time	Memory
314269		Vladth11	Pinball (JOI14_pinball)	C++14	100 / 100	759 ms	90668 KiB

pinball

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "


using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 18;

ll n, m;

struct AllDinamic {
    struct Node {
        ll x;
        Node *l;
        Node *r;
        Node(ll _x) {
            x = _x;
            l = r = NULL;
        }
    };
    ll query(Node* &node, ll st, ll dr, ll a, ll b) {
        if(node == NULL){
            return INF;
        }
        if(a <= st && dr <= b) {

            return node->x;
        }
        ll mid = (st + dr) / 2;
        ll minim = INF;
        if(a <= mid) {
            minim = min(minim, query(node->l, st, mid, a, b));
        }
        if(b > mid) {
            minim = min(minim, query(node->r, mid + 1, dr, a, b));
        }
        return minim;
    }
    void update(Node* &node, ll st, ll dr, ll poz, ll val){
        if(node == NULL){
            node = new Node(val);
        }
        node->x = min(node->x, val);
        if(st == dr){
            //node->x = val;
            return;
        }

        ll mid = (st + dr) / 2;
        if(poz <= mid){
            update(node->l, st, mid, poz, val);
        }else{
            update(node->r, mid + 1, dr, poz, val);
        }
    }
public:
    Node *root;
    ll q(ll a, ll b){
        return query(root, 1, n, a, b);
    }
    void up(ll a, ll b){
        update(root, 1, n, a, b);
    }
}pref, suff;

int main() {
    cin >> m >> n;
    ll maxim = (1LL << 55);
   // debug(suff.q(2, 4));
    for(ll i = 1; i <= m; i++) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll cost = 0, sum = 0;
        cost = pref.q(a, b) + d;
        if(a == 1){
            cost = d;
        }
        sum += cost;
        pref.up(c, cost);
        cost = suff.q(a, b) + d;
        if(b == n){
            cost = d;
        }
        sum += cost;
        suff.up(c, cost);
       // debug(sum);
        maxim = min(maxim, sum - d);
    }
    if(maxim < (1LL << 55)){
        cout << maxim;
    }else{
        cout << -1;
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49