Submission #1011512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011512		Khanhcsp2	Pinball (JOI14_pinball)	C++14	100 / 100	696 ms	402000 KiB

pinball

#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
struct node
{
    node* l;
    node* r;
    int val;
    node()
    {
        l=r=NULL;
        val=1e18;
    }
};
void update(node* pos, int l, int r, int u, int v, int val)
{
    if(l>v||r<u) return;
    if(u<=l && r<=v)
    {
        pos->val=min(pos->val, val);
        return;
    }
    if(pos->l==NULL) pos->l = new node();
    if(pos->r==NULL) pos->r = new node();
    int mid=(l+r)>>1;
    update(pos->l, l, mid, u, v, val);
    update(pos->r, mid+1, r, u, v, val);
    pos->val=min(pos->l->val, pos->r->val);
}
int get(node* pos, int l, int r, int u, int v)
{
    if(l>v||r<u) return 1e18;
    if(u<=l && r<=v)
    {
        return pos->val;
    }
    if(pos->l==NULL) pos->l = new node();
    if(pos->r==NULL) pos->r = new node();
    int mid=(l+r)>>1;
    return min(get(pos->l, l, mid, u, v), get(pos->r, mid+1, r, u, v));
}
int m, n, a, b, c, d;
void sol()
{
    cin >> m >> n;
    node* root1 = new node();
    node* root2 = new node();
    int ans=1e18;
    for(int i=1;i<=m;i++)
    {
        cin >> a >> b >> c >> d;
        int l=0, r=0;
        if(a!=1) l=get(root1, 1, n, a, b);
        if(b!=n) r=get(root2, 1, n, a, b);
        ans=min(ans, l+r+d);
        update(root1, 1, n, c, c, l+d);
        update(root2, 1, n, c, c, r+d);
    }
    if(ans==1e18) cout << -1;
    else cout << ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

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