Submission #814600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
814600	2023-08-08T08:30:04 Z	이종영(#10372)	Arranging Tickets (JOI17_arranging_tickets)	C++17	65 / 100	6000 ms	17828 KB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pii=array<int,2>;
using tii=array<int,3>;
const ll inf=1e18;
const int N=2e5+5;
int n,m;
ll k,in[N],w[N],ans;
vector<pii> v[N];
tii a[N];
struct ST{
	ll T[2*N],D[2*N];
	void init(int nd,int l,int r){
		if(l==r){
			T[nd]=w[l];
			D[nd]=0;
			return;
		}
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		init(ln,l,m); init(rn,m+1,r);
		T[nd]=min(T[ln],T[rn]); 
		D[nd]=0;
	}
	void upd(int nd,int l,int r,int s,int e,ll v){
		if(r<s||e<l) return;
		if(s<=l&&r<=e){
			T[nd]+=v;
			D[nd]+=v;
			return;
		}
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		upd(ln,l,m,s,e,v); upd(rn,m+1,r,s,e,v);
		T[nd]=min(T[ln],T[rn])+D[nd];
	}
	ll qry(int nd,int l,int r,int s,int e){
		if(r<s||e<l) return 1e9;
		if(s<=l&&r<=e) return T[nd];
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		return min(qry(ln,l,m,s,e),qry(rn,m+1,r,s,e))+D[nd];
	}
}T;
ll Do(ll s){
	if(s==2*k) return 1e18;
	ll ret=s;
	for(int i=1;i<=n;i++){
		w[i]=(s-k+in[i])/2;
	}
	T.init(1,1,n);
	for(int r=1;r<n;r++){
		for(auto [l,d]: v[r]){
			ll val=T.qry(1,1,n,l,r);
			if(val==0) break;
			val=min(val,(ll)d);
			T.upd(1,1,n,l,r,-val);
			ret-=val;
		}
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
		if(a[i][0]>a[i][1]) swap(a[i][0],a[i][1]);
		in[a[i][0]]+=a[i][2];
		in[a[i][1]]-=a[i][2];
		v[a[i][1]-1].push_back({a[i][0],a[i][2]});
		k+=a[i][2];
	}
	for(int i=1;i<=n;i++) in[i]+=in[i-1];
	for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end(),greater<>());
	ans=k;
	ll L=k,R=2*k-1;
	while(L<=R){
		ll M=(L+R)>>1;
		ll v1=Do(M),v2=Do(M+1);
		if(v1<=v2){
			ans=min(ans,v1);
			R=M-1;
		} else{
			ans=min(ans,v2);
			L=M+1;
		}
	}
	for(ll i=k;i<=k+100;i++) ans=min(ans,Do(i));
	cout<<ans;
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4960 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4960 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	8 ms	5064 KB	Output is correct
17	Correct	6 ms	5076 KB	Output is correct
18	Correct	6 ms	5096 KB	Output is correct
19	Correct	6 ms	5072 KB	Output is correct
20	Correct	9 ms	4948 KB	Output is correct
21	Correct	6 ms	4948 KB	Output is correct
22	Correct	9 ms	5072 KB	Output is correct
23	Correct	7 ms	4948 KB	Output is correct
24	Correct	6 ms	4948 KB	Output is correct
25	Correct	9 ms	5052 KB	Output is correct
26	Correct	7 ms	5068 KB	Output is correct
27	Correct	6 ms	5072 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4960 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	8 ms	5064 KB	Output is correct
17	Correct	6 ms	5076 KB	Output is correct
18	Correct	6 ms	5096 KB	Output is correct
19	Correct	6 ms	5072 KB	Output is correct
20	Correct	9 ms	4948 KB	Output is correct
21	Correct	6 ms	4948 KB	Output is correct
22	Correct	9 ms	5072 KB	Output is correct
23	Correct	7 ms	4948 KB	Output is correct
24	Correct	6 ms	4948 KB	Output is correct
25	Correct	9 ms	5052 KB	Output is correct
26	Correct	7 ms	5068 KB	Output is correct
27	Correct	6 ms	5072 KB	Output is correct
28	Correct	84 ms	5268 KB	Output is correct
29	Correct	88 ms	5260 KB	Output is correct
30	Correct	95 ms	5268 KB	Output is correct
31	Correct	75 ms	5204 KB	Output is correct
32	Correct	76 ms	5260 KB	Output is correct
33	Correct	74 ms	5268 KB	Output is correct
34	Correct	73 ms	5256 KB	Output is correct
35	Correct	93 ms	5268 KB	Output is correct
36	Correct	87 ms	5204 KB	Output is correct
37	Correct	82 ms	5268 KB	Output is correct
38	Correct	86 ms	5312 KB	Output is correct
39	Correct	86 ms	5288 KB	Output is correct

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4960 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	8 ms	5064 KB	Output is correct
17	Correct	6 ms	5076 KB	Output is correct
18	Correct	6 ms	5096 KB	Output is correct
19	Correct	6 ms	5072 KB	Output is correct
20	Correct	9 ms	4948 KB	Output is correct
21	Correct	6 ms	4948 KB	Output is correct
22	Correct	9 ms	5072 KB	Output is correct
23	Correct	7 ms	4948 KB	Output is correct
24	Correct	6 ms	4948 KB	Output is correct
25	Correct	9 ms	5052 KB	Output is correct
26	Correct	7 ms	5068 KB	Output is correct
27	Correct	6 ms	5072 KB	Output is correct
28	Correct	84 ms	5268 KB	Output is correct
29	Correct	88 ms	5260 KB	Output is correct
30	Correct	95 ms	5268 KB	Output is correct
31	Correct	75 ms	5204 KB	Output is correct
32	Correct	76 ms	5260 KB	Output is correct
33	Correct	74 ms	5268 KB	Output is correct
34	Correct	73 ms	5256 KB	Output is correct
35	Correct	93 ms	5268 KB	Output is correct
36	Correct	87 ms	5204 KB	Output is correct
37	Correct	82 ms	5268 KB	Output is correct
38	Correct	86 ms	5312 KB	Output is correct
39	Correct	86 ms	5288 KB	Output is correct
40	Execution timed out	6017 ms	17828 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4960 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	8 ms	5064 KB	Output is correct
17	Correct	6 ms	5076 KB	Output is correct
18	Correct	6 ms	5096 KB	Output is correct
19	Correct	6 ms	5072 KB	Output is correct
20	Correct	9 ms	4948 KB	Output is correct
21	Correct	6 ms	4948 KB	Output is correct
22	Correct	9 ms	5072 KB	Output is correct
23	Correct	7 ms	4948 KB	Output is correct
24	Correct	6 ms	4948 KB	Output is correct
25	Correct	9 ms	5052 KB	Output is correct
26	Correct	7 ms	5068 KB	Output is correct
27	Correct	6 ms	5072 KB	Output is correct
28	Correct	84 ms	5268 KB	Output is correct
29	Correct	88 ms	5260 KB	Output is correct
30	Correct	95 ms	5268 KB	Output is correct
31	Correct	75 ms	5204 KB	Output is correct
32	Correct	76 ms	5260 KB	Output is correct
33	Correct	74 ms	5268 KB	Output is correct
34	Correct	73 ms	5256 KB	Output is correct
35	Correct	93 ms	5268 KB	Output is correct
36	Correct	87 ms	5204 KB	Output is correct
37	Correct	82 ms	5268 KB	Output is correct
38	Correct	86 ms	5312 KB	Output is correct
39	Correct	86 ms	5288 KB	Output is correct
40	Execution timed out	6017 ms	17828 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-

Submission #814600

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 35.0 / 35.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 20.0

Subtask #5 0 / 15.0

Subtask #1
10.0 / 10.0

Subtask #2
35.0 / 35.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 20.0

Subtask #5
0 / 15.0