QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557533#5425. Proposition CompositionWuyanruWA 229ms26720kbC++144.0kb2024-09-11 10:11:582024-09-11 10:11:59

Judging History

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

  • [2024-09-11 10:11:59]
  • 评测
  • 测评结果:WA
  • 用时:229ms
  • 内存:26720kb
  • [2024-09-11 10:11:58]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int mi[1000001];
int ma[1000001];
int bel[250005];//每一个点对应的链表编号
int root[250005];//链表的链头
int cnt[250005];//链表内元素个数
int nx[250005];
int lt[200005];
set<int>S0,S1;
int n,m,c;
ll ans;
inline void push_up(int p)
{
	mi[p]=min(mi[p*2],mi[p*2|1]);
	ma[p]=max(ma[p*2],ma[p*2|1]);
}
void update(int p,int pl,int pr,int x)
{
	if(pl==pr)
	{
		mi[p]=lt[pl],ma[p]=nx[pl];
		return ;
	}
	int mid=(pl+pr)>>1;
	if(x<=mid) update(p*2,pl,mid,x);
	else update(p*2|1,mid+1,pr,x);
	push_up(p);
}
void find(int p,int pl,int pr,int l,int r,vc<pi>&v)
{
	if(mi[p]>l&&ma[p]<r) return ;
	if(pl==pr)
	{
		if(mi[p]<l) v.push_back(pi(bel[pl],pl));
		if(ma[p]>r) v.push_back(pi(bel[pl],nx[pl]));
		return ;
	}
	int mid=(pl+pr)>>1;
	if(l<=mid) find(p*2,pl,mid,l,r,v);
	if(mid<r) find(p*2|1,mid+1,pr,l,r,v);
}
inline void cover(int l,int r)
{
	auto it=S1.lower_bound(l);
	while(it!=S1.end()&&*it<r) S1.erase(it),it=S1.lower_bound(l);
	it=S0.lower_bound(l);
	while(it!=S0.end()&&*it<r) S1.insert(*it),S0.erase(it),it=S0.lower_bound(l);
}
inline ll C(int c){ return (ll)c*(c-1)/2;}
inline void run(int L,int P1,int P2)
{
	ans-=C(cnt[L]);
	vc<int>v[2];int i=root[L],j=P1,f=-1;//哪个小
	while(true)
	{
		v[0].push_back(i),v[1].push_back(j);
		if(nx[i]==i){ f=0;break;}
		else if(nx[j]==P2){ f=1;break;}
		i=nx[i]==P1?P2:nx[i],j=nx[j];
	}
	int N1=lt[P1],N2=lt[P2];
	lt[P1]=P1,nx[N2]=N2;nx[N1]=P2,lt[P2]=N1;
	update(1,1,n,P1),update(1,1,n,P2);
	update(1,1,n,N1),update(1,1,n,N2);

	c++;cnt[c]=0;
	root[c]=v[f].front();
	for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
	ans+=C(cnt[L])+C(cnt[c]);
}
inline void run(int L,int P)
{
	ans-=C(cnt[L]);
	vc<int>v[2];int i=root[L],j=P,f=-1;
	while(true)
	{
		v[0].push_back(i),v[1].push_back(j);
		if(nx[i]==P){ f=0;break;}
		else if(nx[j]==j){ f=1;break;}
		i=nx[i],j=nx[j];
	}
	int N=lt[P];
	nx[N]=N,lt[P]=P;
	update(1,1,n,N),update(1,1,n,P);

	c++;cnt[c]=0;
	root[c]=v[f].front();
	for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
	ans+=C(cnt[L])+C(cnt[c]);
	root[L]=v[1-f].front();
}
inline void run()
{
	int l=read(),r=read();
	if(l>r) swap(l,r);
	if(l==r) return ;

	vc<pi>v;find(1,1,n,l,r-1,v);cover(l,r);
	sort(v.begin(),v.end());

	// for(auto i:v) printf("(%d,%d)\n",i.first,i.second);
	for(unsigned i=0;i<v.size();i++)
	{
		if(i+1<v.size()&&v[i].first==v[i+1].first)
		{
			run(v[i].first,v[i].second,v[i+1].second);
			i++;
		}
		else run(v[i].first,v[i].second);
	}
}
inline void output()
{
	return ;
	printf("output ans=%lld %d %d\n",ans,(int)S0.size(),(int)S1.size());
	printf("S0 : ");for(int i:S0) printf("%d ",i);;putchar('\n');
	printf("S1 : ");for(int i:S1) printf("%d ",i);;putchar('\n');
	for(int i=1;i<n;i++) printf("i=%d : bel=%d lt=%d nx=%d\n",i,bel[i],lt[i],nx[i]);
	for(int i=1;i<=c;i++) printf("%d : cnt=%d root=%d\n",i,cnt[i],root[i]);
}
inline void solve()
{
	S0.clear(),S1.clear();
	n=read(),m=read(),c=0;
	if(n==1)
	{
		for(int i=1;i<=m;i++)
		{
			assert(read()==1&&read()==1);
			printf("0\n");
		}
		return ;
	}

	c=1;cnt[1]=n-1,root[1]=1,ans=C(n-1);
	for(int i=1;i<n;i++)
	{
		nx[i]=min(n-1,i+1);
		lt[i]=max(1,i-1);
		bel[i]=1;
		update(1,1,n,i);
		S0.insert(i);
	}
	output();

	for(int i=1;i<=m;i++)
	{
		run();
		ll o=ans+(ll)S0.size()*(n-1-S0.size()+i)+S1.size();
		printf("%lld\n",o);output();
	}
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9980kb

input:

3
4 3
2 4
4 2
3 3
7 3
3 4
1 2
1 7
6 4
1 3
4 6
2 5
3 4

output:

6
5
6
21
24
10
15
12
3
2

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 34ms
memory: 9912kb

input:

45540
10 9
10 1
1 10
10 1
1 10
1 10
10 1
1 10
3 3
10 1
10 4
1 2
1 10
3 4
1 10
7 6
7 1
5 6
1 7
6 6
7 1
6 7
9 7
3 3
7 7
5 4
1 1
9 1
9 1
6 5
8 7
1 8
4 4
5 6
1 1
1 8
6 6
4 5
3 3
3 2
3 1
3 3
3 9
3 1
3 3
2 2
3 3
3 1
2 2
1 1
2 3
3 1
10 1
2 1
7 1
1 7
3 8
1 3
1 3
3 3
1 3
2 2
1 3
1 3
3 3
3 6
3 1
1 3
1 3
1 3
1...

output:

45
36
36
36
36
36
36
36
36
45
36
28
21
21
15
10
10
10
6
36
44
50
57
28
21
15
28
28
21
21
15
15
10
3
1
1
3
3
3
3
1
1
1
0
0
45
21
3
1
1
1
1
1
1
1
3
1
1
1
1
1
45
36
36
36
36
36
36
36
3
3
1
0
0
0
0
0
0
3
1
0
0
15
10
10
0
0
0
0
0
0
0
0
28
34
21
6
6
6
6
1
0
0
21
15
15
0
0
0
0
0
0
0
45
53
0
0
0
0
0
0
0
0
1...

result:

ok 249586 numbers

Test #3:

score: 0
Accepted
time: 86ms
memory: 9896kb

input:

2507
86 4
41 41
36 36
31 30
86 1
110 22
1 110
110 1
11 11
110 1
110 1
110 1
1 110
107 106
72 72
106 106
74 74
1 110
110 1
58 58
110 1
110 1
1 110
101 100
110 1
100 100
110 1
8 7
114 180
114 1
114 1
114 1
1 114
1 114
114 1
37 38
49 48
105 106
1 114
90 90
1 114
9 9
114 1
67 68
20 20
114 1
1 114
54 55
...

output:

3655
3740
3823
3570
5995
5886
5886
5886
5886
5886
5886
5778
5778
5778
5778
5778
5778
5778
5778
5778
5778
5671
5671
5671
5671
5565
6441
6328
6328
6328
6328
6328
6216
6105
5995
5995
5995
5995
5995
5995
5886
5886
5886
5886
5778
5671
5671
5565
5565
5460
5460
5460
5460
5460
5356
5253
5253
5253
5151
5151
...

result:

ok 249877 numbers

Test #4:

score: 0
Accepted
time: 142ms
memory: 18872kb

input:

3
82425 27858
30801 30802
1 82425
73850 73850
1 82425
65949 65949
82425 1
76026 76025
61936 61936
82425 1
82425 1
82425 1
6504 6504
82425 1
25155 25156
79743 79743
1 82425
69406 69406
29247 29247
18351 18351
23171 23170
29704 29703
82425 1
1 82425
82425 1
74918 74917
22395 22394
893 894
82425 1
391 ...

output:

3396899100
3396816676
3396816676
3396734253
3396734253
3396734253
3396651831
3396651831
3396651831
3396651831
3396651831
3396651831
3396651831
3396569410
3396569410
3396569410
3396569410
3396569410
3396569410
3396486990
3396404571
3396404571
3396404571
3396404571
3396322153
3396239736
3396157320
339...

result:

ok 116748 numbers

Test #5:

score: -100
Wrong Answer
time: 229ms
memory: 26720kb

input:

1
250000 250000
248617 248617
1 250000
47808 47809
1 250000
1 250000
110493 110494
1 250000
66675 66676
141326 141327
250000 1
115279 115280
193218 193219
250000 1
77714 77715
1 250000
1 250000
212943 212943
223061 223060
1 250000
250000 1
1 250000
71059 71059
1 250000
246523 246522
1 250000
88700 8...

output:

31249875000
31249875000
31249625001
31249375003
31249375003
31249125006
31249125006
31248875010
31248625015
31248625015
31248375021
31248125028
31248125028
31247875036
31247875036
31247875036
31247875036
31247625045
31247625045
31247625045
31247625045
31247625045
31247625045
31247375055
31247375055
...

result:

wrong answer 4475th numbers differ - expected: '30971000521', found: '30932945137'