QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469160#8567. Cheap ConstructionPhantomThreshold#WA 198ms12064kbC++201.8kb2024-07-09 15:10:452024-07-09 15:10:45

Judging History

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

  • [2024-07-09 15:10:45]
  • 评测
  • 测评结果:WA
  • 用时:198ms
  • 内存:12064kb
  • [2024-07-09 15:10:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn = 510000;

int n,Q;
int a[maxn];
int pi[maxn],hi[maxn];
int seg[maxn<<2];

int sum[maxn];
void add(int x,int c)
{
	for(;x<=n;x+=lowbit(x)) sum[x]+=c;
}
int query(int x)
{
	int ret=0;
	for(;x;x-=lowbit(x)) ret+=sum[x];
	return ret;
}

void build(const int x,const int l,const int r)
{
	if(l==r)
	{
		seg[x]=a[l];
		return;
	}
	int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
	build(lc,l,mid); build(rc,mid+1,r);
	seg[x]=min(seg[lc],seg[rc]);
}
set< pair<int,int> >S;
int lx,rx;
int query(const int x,const int l,const int r)
{
	if(rx<l||r<lx) return INT_MAX;
	if(lx<=l&&r<=rx) return seg[x];
	int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
	return min( query(lc,l,mid), query(rc,mid+1,r) );
}
int findmin(const int l,const int r)
{
	lx=l,rx=r; int cc=query(1,1,n);
	auto temp=make_pair(cc,r);
	auto it= S.upper_bound(temp); it--;
	return it->second;
}

vector< pair<int,int> >ans;
void solve(const int l,const int r,const int left)
{
	if(l>r) return;
	int mid=findmin(l,r);
	ans.emplace_back(left+1,a[mid]);
	solve(l,mid-1,left);
	solve(mid+1,r,left+mid-l+1);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>pi[i]>>hi[i];
		}
		for(int i=0;i<=n;i++) sum[i]=0;
		for(int i=n;i>=1;i--)
		{
			pi[i]+=query(pi[i]);
			add(pi[i],1);
		}
		for(int i=1;i<=n;i++) a[pi[i]]=hi[i];
		build(1,1,n);
		set< pair<int,int> >_; S.swap(_);
		for(int i=1;i<=n;i++) S.insert( make_pair(a[i],i) );
		
		vector< pair<int,int> >__; ans.swap(__);
		solve(1,n,0);
		for(auto [u,v]:ans) cout<<u<<' '<<v<<'\n';
	}
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11816kb

input:

1
3
1 1
2 2
1 3

output:

1 1
1 3
3 2

result:

ok 3 lines

Test #2:

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

input:

2
3
1 1
1 2
3 1
3
1 3
2 1
3 3

output:

1 1
1 1
1 2
1 1
1 3
3 3

result:

ok 6 lines

Test #3:

score: -100
Wrong Answer
time: 198ms
memory: 12064kb

input:

1000
500
1 25
2 115
2 356
4 396
5 417
3 416
1 376
8 302
5 475
8 134
5 470
2 191
9 443
9 483
7 311
6 415
14 422
6 288
9 411
9 318
18 406
20 213
16 292
8 351
8 150
20 199
3 311
22 321
22 221
16 364
7 316
17 79
23 160
23 369
6 209
36 9
35 490
2 498
30 391
31 175
10 322
16 484
4 63
44 304
39 300
13 309
...

output:

1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
...

result:

wrong answer 1st lines differ - expected: '1 2', found: '1 0'