Submission #1287493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287493		trinm01	Pinball (JOI14_pinball)	C++20	11 / 100	32 ms	31720 KiB

pinball

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 5e5 + 5;
const ll oo = 1e18 + 7;  
const int base = 10;

int N;
struct segtree{
	int st[4*MAXN];
	void init(){
		FOR(i, 0, 4*N){
			st[i]=oo;
		}
	}
	void update(int id, int l, int r, int i, int val){
		if(l>i || r<i){
			return;
		}
		if(l>=r){
			st[id]=min(st[id], val);
			return;
		}
		int mid=(l+r)/2;
		update(id*2, l, mid, i, val);
		update(id*2+1, mid+1, r, i, val);
		st[id]=min(st[id*2], st[id*2+1]);
	}
	int get(int id, int l, int r, int i, int j){
		if(l>j || r<i){
			return oo;
		}
		if(l>=i && r<=j){
			return st[id];
		}
		int mid=(l+r)/2;
		return min(get(id*2, l, mid, i, j), get(id*2+1, mid+1, r, i, j));
	}
};
segtree T1, T2;

int m, n;
struct node{
	int l, r, p, c;
}a[MAXN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    // freopen("test.txt", "r", stdin);
    // freopen("o2.out", "w", stdout);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> m >> n;
    FOR(i, 1, m){
    	int l, r, p, c;
    	cin >> l >> r >> p >> c;
    	a[i]={l, r, p, c};
    }
    vector<int> nen;
    FOR(i, 1, m){
    	nen.push_back(a[i].l);
    	nen.push_back(a[i].r);
    	nen.push_back(a[i].p);
    }
    nen.push_back(1);
    nen.push_back(n);
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    FOR(i, 1, n){
    	a[i].l=lower_bound(nen.begin(), nen.end(), a[i].l)-nen.begin()+1;
    	a[i].r=lower_bound(nen.begin(), nen.end(), a[i].r)-nen.begin()+1;
    	a[i].p=lower_bound(nen.begin(), nen.end(), a[i].p)-nen.begin()+1;
    }
	N=lower_bound(nen.begin(), nen.end(), n)-nen.begin()+1;
    
    T1.init();
    T2.init();
    T1.update(1, 1, N, 1, 0);
    T2.update(1, 1, N, N, 0);
    int ans=oo;
    FOR(i, 1, m){
    	auto [l, r, p, c]=a[i];
    	int vl1=T1.get(1, 1, N, l, r);
    	int vl2=T2.get(1, 1, N, l, r);
    	ans=min(ans, vl1+vl2+c);
    	T1.update(1, 1, N, p, vl1+c);
    	T2.update(1, 1, N, p, vl2+c);
    }
    
    if(ans==oo) ans=-1;
    cout << ans;
    
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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