QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469160 | #8567. Cheap Construction | PhantomThreshold# | WA | 198ms | 12064kb | C++20 | 1.8kb | 2024-07-09 15:10:45 | 2024-07-09 15:10:45 |
Judging History
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'