oj.uz

Submission #814555

# Submission time Handle Problem Language Result Execution time Memory
814555 2023-08-08T08:19:52 Z 이종영(#10372) Arranging Tickets (JOI17_arranging_tickets) C++17
0 / 100
 3 ms 4948 KB 
#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;
int in[N],w[N],ans;
vector<int> v[N];
tii a[N];
struct ST{
	int 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,int 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];
	}
	int 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;
int Do(int s){
	if(s==n+m) return 1e9;
	int ret=s;
	for(int i=1;i<=n;i++){
		w[i]=s-m+in[i];
		w[i]/=2;
	}
	T.init(1,1,n);
	for(int r=1;r<n;r++){
		for(int l: v[r]){
			if(T.qry(1,1,n,l,r)==0) break;
			T.upd(1,1,n,l,r,-1);
			ret--;
		}
	}
	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].emplace_back(a[i][0]);
	}
	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=m;
	int L=m,R=n+m-1;
	while(L<=R){
		int M=(L+R)>>1;
		int 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(int i=m;i<=n+m-1;i++){
		int v=Do(i);
		debug(i,v);
		ans=min(ans,v);
	}*/
	cout<<ans;
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 15.0

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