QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#682950#9524. 1D Galaxyucup-team3586#WA 1ms9852kbC++237.0kb2024-10-27 18:06:152024-10-27 18:06:15

Judging History

你现在查看的是最新测评结果

  • [2024-10-27 18:06:15]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：9852kb
查看
  • [2024-10-27 18:06:15]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rng(114514);
int n,q;
ll x[100100],w[100100],s[100100];
ll mn[100100],mx[100100];
struct query
{
	ll t;
	int ind,x;
	bool friend operator <(const query &a,const query &b){return a.t<b.t;}
};
vector<query> vec;
ull prior[100100];
int ls[100100],rs[100100];
int tag[100100];
int siz[100100];
int fa[100100];
void pushup(int x)
{
	s[x]=s[ls[x]]+s[rs[x]]+w[x];
	siz[x]=siz[ls[x]]+siz[rs[x]]+1;
	mn[x]=(ls[x]?mn[ls[x]]:(::x[x]));
	mx[x]=(rs[x]?mx[rs[x]]:(::x[x]));
	fa[ls[x]]=fa[rs[x]]=x;
}
void pushdown(int u)
{
	x[u]+=tag[u];
	mn[u]+=tag[u];
	mx[u]+=tag[u];
	if(ls[u]) tag[ls[u]]+=tag[u];
	if(rs[u]) tag[rs[u]]+=tag[u];
	tag[u]=0;
}
int merge(int u,int v)
{
	if(!u||!v)
	{
		pushup(u+v);
		return u+v;
	}
	if(prior[u]>prior[v])
	{
		pushdown(u);
		rs[u]=merge(rs[u],v);
		pushup(u);
		return u;
	}
	else
	{
		pushdown(v);
		ls[v]=merge(u,ls[v]);
		pushup(v);
		return v;
	}
}
void splits(int u,int s,int &a,int &b)
{
	if(!u)
	{
		a=b=0;
		return ;
	}
	pushdown(u);
	if(siz[u]+1<=s)
	{
		a=u;
		splits(rs[u],s-siz[u]-1,rs[a],b);
		pushup(a);
		return ;
	}
	else
	{
		b=u;
		splits(ls[u],s,a,ls[b]);
		pushup(b);
		return ;
	}
}
void splitv(int u,ll v,int &a,int &b)
{
	if(!u)
	{
		a=b=0;
		return ;
	}
	pushdown(u);
	if(s[ls[u]]+w[u]<=v)
	{
		a=u;
		splitv(rs[u],v-w[u]-s[ls[u]],rs[a],b);
		pushup(a);
		return ;
	}
	else
	{
		b=u;
		splitv(ls[u],v,a,ls[b]);
		pushup(b);
		return ;
	}
}
void splitx(int u,int p,int &a,int &b)
{
	if(!u)
	{
		a=b=0;
		return ;
	}
	pushdown(u);
	if(x[u]<=p)
	{
		a=u;
		splitx(rs[u],p,rs[a],b);
		pushup(a);
		return ;
	}
	else
	{
		b=u;
		splitx(ls[u],p,a,ls[b]);
		pushup(b);
		return ;
	}
}
void pushdown_all(int x)
{
	pushdown(x);
	if(ls[x]) pushdown_all(ls[x]);
	if(rs[x]) pushdown_all(rs[x]);
}
int getx(int ind)
{
	int res=x[ind];
	while(true)
	{
		res+=tag[ind];
		if(ind==ls[fa[ind]]||ind==rs[fa[ind]])
			ind=fa[ind];
		else
			break;
	}
	return res;
}
int ans[100100];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>w[i];
	mn[0]=inf;
	mx[0]=-inf;
	for(int i=1;i<=q;i++)
	{
		query tmp;
		cin>>tmp.t>>tmp.x;
		tmp.ind=i;
		vec.pb(tmp);
	}
	srt(vec);
	int rt=0;
	for(int i=1;i<=n;i++)
	{
		prior[i]=rng();
		siz[i]=1;
		s[i]=w[i];
		mn[i]=mx[i]=x[i];
		int A,B;
		splitx(rt,x[i],A,B);
		rt=merge(A,merge(i,B));
	}
	ll cur=0;
	int qp=0;
	ll total=accumulate(w+1,w+n+1,0ll);
	while(true)
	{
		if(mn[rt]==mx[rt])
		{
			while(qp<sz(vec))
			{
				ans[vec[qp].ind]=x[rt];
				qp++;
			}
			break;
		}
		if(mn[rt]==mx[rt]-1)
		{
			pushdown_all(rt);
			while(qp<sz(vec))
			{
				int sind=vec[qp].x;
				int ori=x[sind];
				if((vec[qp].t-cur)&1)
					ori=mn[rt]+mx[rt]-ori;
				ans[vec[qp].ind]=ori;
				qp++;
			}
			break;
		}
		ll half=total/2;
		int A,B,C;
		int ppos;
		splitv(rt,half,A,C);
		ppos=mx[A];
		rt=merge(A,C);
		splitx(rt,ppos,A,B);
		splitx(B,mn[B],B,C);
		if(s[A]==s[C])
		{
			ll need=min(x[B]-mx[A],mn[C]-x[B]);
			while(qp<sz(vec)&&vec[qp].t<=cur+need)
			{
				int sind=vec[qp].x;
				int qind=vec[qp].ind;
				ll T=vec[qp].t-cur;
				int X=getx(sind);
				if(X==x[B])
					ans[qind]=X;
				else if(X<x[B])
					ans[qind]=X+T;
				else
					ans[qind]=X-T;
				qp++;
			}
			cur+=need;
			tag[A]+=need;
			tag[C]-=need;
			rt=merge(A,merge(B,C));
		}
		else
		{
			if(s[A]>s[C])
				C=merge(B,C);
			else
				A=merge(A,B);
			ll X1=mx[A];
			ll X2=mn[C];
			if((X2-X1)%2==0)
			{
				ll need=(X2-X1)/2;
				while(qp<sz(vec)&&vec[qp].t<=cur+need)
				{
					int sind=vec[qp].x;
					int qind=vec[qp].ind;
					ll T=vec[qp].t-cur;
					int X=getx(sind);
					if(X<=X1)
						ans[qind]=X+T;
					else
						ans[qind]=X-T;
					qp++;
				}
				cur+=need;
				tag[A]+=need;
				tag[C]-=need;
				rt=merge(A,C);
			}
			else
			{
				int S1,S2,S3,S4;
				ll need=(X2-X1)/2;
				while(qp<sz(vec)&&vec[qp].t<=cur+need)
				{
					int sind=vec[qp].x;
					int qind=vec[qp].ind;
					ll T=vec[qp].t-cur;
					int X=getx(sind);
					if(X<=X1)
						ans[qind]=X+T;
					else
						ans[qind]=X-T;
					qp++;
				}
				cur+=need;
				tag[A]+=need;
				tag[C]-=need;
				pushdown(A);
				pushdown(C);
				splitx(A,mx[A]-1,S1,S2);
				splitx(C,mn[C],S3,S4);
				if(mx[S1]==mx[S2]-1||mn[S3]+1==mn[S4])
				{
					tag[S1]++;
					tag[S4]--;
					rt=merge(S1,S4);
					tag[S2]++;
					tag[S3]--;
					pushdown(S2);
					pushdown(S3);
					int tmpA,tmpB;
					splitx(rt,mn[S2],tmpA,tmpB);
					rt=merge(tmpA,merge(S2,tmpB));
					splitx(rt,mn[S3],tmpA,tmpB);
					rt=merge(tmpA,merge(S3,tmpB));
					cur++;
					while(qp<sz(vec)&&vec[qp].t==cur)
					{
						int sind=vec[qp].x;
						int qind=vec[qp].ind;
						ans[qind]=getx(sind);
						qp++;
					}
				}
				else
				{
					if(s[S1]>=s[S2]+s[S4]||s[S4]>=s[S1]+s[S3])
					{
						tag[S1]++;
						tag[S4]--;
						rt=merge(S1,S4);
						tag[S2]++;
						tag[S3]--;
						pushdown(S2);
						pushdown(S3);
						int tmpA,tmpB;
						splitx(rt,mn[S2],tmpA,tmpB);
						rt=merge(tmpA,merge(S2,tmpB));
						splitx(rt,mn[S3],tmpA,tmpB);
						rt=merge(tmpA,merge(S3,tmpB));
						cur++;
						while(qp<sz(vec)&&vec[qp].t==cur)
						{
							int sind=vec[qp].x;
							int qind=vec[qp].ind;
							ans[qind]=getx(sind);
							qp++;
						}
						continue;
					}
					ll need=min(mx[S2]-mx[S1],mn[S4]-mn[S3]);
					int XX1=x[S2],XX2=x[S3];
					while(qp<sz(vec)&&vec[qp].t<=cur+need)
					{
						int sind=vec[qp].x;
						int qind=vec[qp].ind;
						ll T=vec[qp].t-cur;
						int X=getx(sind);
						if(X<XX1)
							ans[qind]=X+T;
						else if(X>XX2)
							ans[qind]=X-T;
						else if(X==XX1)
							ans[qind]=(T&1)?XX2:XX1;
						else
							ans[qind]=(T&1)?XX1:XX2;
						qp++;
					}
					cur+=need;
					if(need&1)
					{
						tag[S2]++;
						tag[S3]--;
					}
					tag[S1]+=need;
					tag[S4]-=need;
					rt=merge(S1,S4);
					pushdown(S2);
					pushdown(S3);
					int tmpA,tmpB;
					splitx(rt,mn[S2],tmpA,tmpB);
					rt=merge(tmpA,merge(S2,tmpB));
					splitx(rt,mn[S3],tmpA,tmpB);
					rt=merge(tmpA,merge(S3,tmpB));
				}
			}
		}
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7844kb

input:

4 12
0 1
1 2
-1 3
2 2
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4

output:

0
1
-1
2
1
0
0
1
0
1
1
0

result:

ok 12 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 9732kb

input:

5 5
-4 5
-1 3
5 5
0 4
-4 2
0 3
3 1
5 5
1 3
3 3

output:

5
-1
1
4
2

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 7700kb

input:

5 5
3 2
1 3
0 3
1 5
0 5
7 1
1 4
1 5
8 5
10 3

output:

0
0
1
0
0

result:

ok 5 lines

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 9852kb

input:

5 5
-3 2
-2 1
5 3
0 1
1 5
10 5
3 1
1 3
2 3
8 4

output:

1
0
4
3
1

result:

wrong answer 5th lines differ - expected: '0', found: '1'
English 繁體中文 简体中文

伺服器時間: 2024-12-12 10:42:08 | 開源專案