oj.uz

Submission #749768

# Submission time Handle Problem Language Result Execution time Memory
749768 2023-05-28T13:07:05 Z Dan4Life Treatment Project (JOI20_treatment) C++17
0 / 100
 79 ms 5580 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const int mxM = (int)1e5+2;
const ll LINF = (ll)1e18;
using pii = pair<ll,int>;

int n, m;
vector<pii> v;
ll dis[mxM], seg[mxM*2];
struct Project{ int t, l, r, c; } a[mxM];
priority_queue<pii,vector<pii>,greater<pii>> pq;

void upd(int x, int p=0, int l=0, int r=m-1){
	if(l==r){ seg[p] = a[l].l+a[l].t; return; }
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,p+1,l,mid);
	else upd(x,rp,mid+1,r);
	seg[p] = min(seg[p+1],seg[rp]);
}

void query(int i, int j, int k, int p=0, int l=0, int r=m-1){
	if(i<a[l].l-a[l].t or j < seg[p]) return;
	if(l==r){
		if(dis[l]==LINF) dis[l] = k+a[l].c, pq.push({dis[l],l});
		seg[p]=LINF; return;
	}
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	query(i,j,k,p+1,l,mid); query(i,j,k,rp,mid+1,r);
	seg[p] = min(seg[p+1],seg[rp]);
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; 
	for(int i = 0; i < m; i++) 
		cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
	sort(a,a+m,[&](Project x, Project y){
		if(x.l-x.t==y.l-y.t) return x.l+x.t < y.l+y.t;
		return x.l-x.t < y.l-y.t;
	});
	for(int i = 0; i < m; i++) 
		if(a[i].l==1) v.pb({i,a[i].c});
	fill(dis,dis+m,LINF); fill(seg,seg+2*m,LINF);
	for(auto [u,w] : v) dis[u]=w, pq.push({w,u});
	for(int i = 0; i < m; i++) upd(i);
	while(!pq.empty()){
		auto [D,s] = pq.top(); pq.pop();
		query(a[s].r-a[s].t+1, a[s].r+a[s].t+1, D);
	}
	ll ans = LINF;
	for(int i = 0; i < m; i++) 
		if(a[i].r==n) ans=min(ans,dis[i]);
	cout << (ans==LINF?-1:ans);
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

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