Submission #340172

#	Time	Username	Problem	Language	Result	Execution time	Memory
340172		YJU	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	6 ms	9708 KiB

arranging_tickets

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll ma[4*N],tag[4*N],n,x,y,c,m,ans;
vector<pll> st[N],ed[N];
vector<pair<pll,ll> > one;

void push(ll id){
	if(tag[id]){
		tag[(id<<1)]+=tag[id];
		tag[(id<<1)+1]+=tag[id];
		ma[(id<<1)]+=tag[id];
		ma[(id<<1)+1]+=tag[id];
		tag[id]=0;
	}
}

void add(ll id,ll l,ll r,ll ql,ll qr,ll del){
	if(l>=ql&&r<=qr){ma[id]+=del;tag[id]+=del;return ;}
	if(l>=qr||r<=ql)return ;
	ll mid=(l+r)>>1;
	push(id);
	add((id<<1),l,mid,ql,qr,del);
	add((id<<1)+1,mid,r,ql,qr,del);
	ma[id]=max(ma[(id<<1)],ma[(id<<1)+1]);
}

ll q(ll id,ll l,ll r,ll to){
	if(l==r-1){return ma[id];}
	ll mid=(l+r)>>1;
	push(id);
	if(to<mid){
		return q(id<<1,l,mid,to);
	}else{
		return q((id<<1)+1,mid,r,to);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP(i,m){
		cin>>x>>y>>c;
		if(y<x)swap(y,x);
		add(1,1,n+1,x,y,c);
		st[x].pb(mp(y,c));
		ed[y].pb(mp(x,c));
		one.pb(mp(mp(x,y),c));
	}
	//REP1(j,n)cout<<q(1,1,n+1,j)<<(j==n?"\n":" ");
	ans=ma[1];
	//cout<<ma[1]<<"\n";
	REP1(i,n){
		for(auto j:st[i]){
			add(1,1,n+1,1,n+1,j.Y);
			add(1,1,n+1,i,j.X,2*-j.Y);
		}
		for(auto j:ed[i]){
			add(1,1,n+1,1,n+1,-j.Y);
			add(1,1,n+1,j.X,i,2*j.Y);
		}
		ans=min(ans,ma[1]);
	}
	for(auto i:one){
		add(1,1,n+1,1,n+1,i.Y);
		add(1,1,n+1,i.X.X,i.X.Y,2*-i.Y);
		ans=min(ans,ma[1]);
		add(1,1,n+1,1,n+1,-i.Y);
		add(1,1,n+1,i.X.X,i.X.Y,2*i.Y);
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15