Submission #57088663

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i(l),i##End(r); i<=i##End; ++i)
#define rep_(i,l,r) for(int i(l),i##End(r); i<i##End; ++i)
#define per(i,l,r) for(int i(r),i##End(l); i>=i##End; --i)
#define per_(i,l,r) for(int i(r),i##End(l); i>i##End; --i)
#define kid(i,x,G) for(int i=G.ls[x];i;i=G.nx[i])
#define endl '\n'
using namespace std;
using ll=long long;
using ull=long long unsigned;
using uint=unsigned int;
using db=double;
using ldb=long double;
using i128=__int128;
using ui128=unsigned __int128;
using bo=bool;
template<typename T> constexpr T inf = 0;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr db inf<db> = 1e18;
template<> constexpr ldb inf<ldb> = 1e18;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i(l),i##End(r); i<=i##End; ++i)
#define rep_(i,l,r) for(int i(l),i##End(r); i<i##End; ++i)
#define per(i,l,r) for(int i(r),i##End(l); i>=i##End; --i)
#define per_(i,l,r) for(int i(r),i##End(l); i>i##End; --i)
#define kid(i,x,G) for(int i=G.ls[x];i;i=G.nx[i])
#define endl '\n'
using namespace std;
using ll=long long;
using ull=long long unsigned;
using uint=unsigned int;
using db=double;
using ldb=long double;
using i128=__int128;
using ui128=unsigned __int128;
using bo=bool;
template<typename T> constexpr T inf = 0;
template<> constexpr int inf<int> = 1e9;
template<> constexpr ll inf<ll> = 1e18;
template<> constexpr db inf<db> = 1e18;
template<> constexpr ldb inf<ldb> = 1e18;
constexpr db eps=1e-12;
#define vec vector
template<typename T> using heap=priority_queue<T,vec<T>,greater<T>>;
template<typename T> using big_heap=priority_queue<T>;
#define clock() chrono::steady_clock::now()
const auto start_time=clock();
template<typename T=db> T runtime() {return chrono::duration<T>(clock()-start_time).count();}
mt19937 rnd(random_device{}());
void Yes(bo f=true) {cout<<(f?"Yes":"No")<<endl;}
void No(bo f=true) {Yes(!f);}
void yes(bo f=true) {cout<<(f?"yes":"no")<<endl;}
void no(bo f=true) {yes(!f);}
void YES(bo f=true) {cout<<(f?"YES":"NO")<<endl;}
void NO(bo f=true) {YES(!f);}
ll qpow(ll a,ll n,ll p)
{
	ll x=1;
	for(;n;n>>=1,a=(i128)a*a%p)
		if(n&1) x=(i128)x*a%p;
	return x;
}
constexpr int
	N=2e5+5,
	M=2e9,
	K=1e7,
	Q=0,
	S=0,
	P=998244353 //1e9+7
;
struct Graph
{
	int e[M],ls[N],nx[M],em;
	void lian(int x,int y) {e[++em]=y,nx[em]=ls[x],ls[x]=em;}
};
struct v_Graph
{
	int e[M][2],ls[N],nx[M],em;
	void lian(int x,int y,int z) {e[++em][0]=y,e[em][1]=z,nx[em]=ls[x],ls[x]=em;}
};
// #define MULTITEST
// #define FILE_IO_NAME ""

#define Y int x,int y,int p
#define D int mid=(x+y)/2
#define ls x,mid,sl[p]
#define rs mid+1,y,sr[p]
int rt[N],t[K],sz,sl[K],sr[K];
int fnd(Y,int l,int r)
{
	if(p==0||x>r||y<l) return 0;
	if(l<=x&&y<=r) return t[p];
	D;return max(fnd(ls,l,r),fnd(rs,l,r));
}
int cng(Y,int w,int v)
{
	if(p==0) p=++sz;
	if(x==y) {t[p]=max(t[p],v);return p;}
	D;
	if(mid>=w) sl[p]=cng(ls,w,v);
	else sr[p]=cng(rs,w,v);
	t[p]=max(t[sl[p]],t[sr[p]]);
	return p;
}

int n,m,w[N];
struct Node {int x,y,s,t,id;}a[N];
bool cmp(Node x,Node y) {return x.s<y.s;}
void _main()
{
	cin>>n>>m>>w[1];
	rep(i,1,m) cin>>a[i].x>>a[i].y>>a[i].s>>a[i].t,a[i].id=i;
	sort(a+1,a+m+1,cmp);
	rep(i,1,m)
	{
		if(a[i].id!=1) w[a[i].id]=max(0,fnd(1,M,rt[a[i].x],0,a[i].s)-a[i].s);
		rt[a[i].y]=cng(1,M,rt[a[i].y],a[i].t,a[i].t+w[a[i].id]);
	}
	rep(i,2,m) cout<<w[i]<<" ";
}

int main() {
#if defined(FILE_IO_NAME) && !defined(ONLINE_JUDGE)
	freopen(FILE_IO_NAME".in","r",stdin);
	freopen(FILE_IO_NAME".out","w",stdout);
#endif
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cout<<fixed<<setprecision(15);
	int T=1;
#if defined(MULTITEST)
	cin>>T;
#endif
	while(T--) _main();
	return 0;
}

Submission Info

Judge Result