QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #646519 | #6434. Paimon Sorting | hhdhh | AC ✓ | 129ms | 6420kb | C++23 | 2.1kb | 2024-10-17 00:12:36 | 2024-10-17 00:12:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
const int N=1e5+10;
int a[N];
int b[N];
int c[N];
int u[N];
LL s[N];
bool bo[N];
void add(int x,int s)//不能0开始
{
x++;
for(;x<N;x+=x&-x)
c[x]+=s;
}
int ask(int x)
{
x++;
int su=0;
for(;x;x-=x&-x)
su+=c[x];
return su;
}
void slove()
{
int n;
cin>>n;
rep(i,1,n)
{
cin>>a[i];
}
stack<PII>se;
rep(i,1,n)
{
while(se.size()&&se.top().fi<a[i])
{
b[se.top().sec]=i;
// debug(se.top().sec);
se.pop();
}
se.push({a[i],i});
}
rep(i,1,n)
{
if(i!=1&&ask(a[i]-1)==ask(N-1))
{
s[i]+=2;
}
else if(i!=1)
{
if(ask(a[i])==ask(N-1))
{
// debug(i);debug(b[i]);
if(b[i]&&u[a[i]]==1)
s[b[i]]+=b[i]-i;
}
else
{
s[i]+=ask(N-1)-ask(a[i]);
}
}
if(bo[a[i]]==0)
{
bo[a[i]]=1;
add(a[i],1);
}
u[a[i]]++;
}
rep(i,1,n)
{
s[i]+=s[i-1];
cout<<s[i]<<" \n"[n==i];
}
rep(i,1,n)
{
if(bo[a[i]])
{
bo[a[i]]=0;
add(a[i],-1);
}
s[i]=b[i]=0;
u[a[i]]=0;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// cout << fixed << setprecision(9);
int t=1;
cin>>t;
while(t--)
{
slove();
}
return 0;
}
//#pragma GCC optimize(2)
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
3 5 2 3 2 1 5 3 1 2 3 1 1
output:
0 2 3 5 7 0 2 4 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 129ms
memory: 6420kb
input:
6107 19 10 13 8 8 11 18 12 9 15 19 6 13 11 11 17 9 14 2 18 12 1 8 10 2 10 2 6 1 5 9 5 7 16 14 4 2 15 12 14 10 3 2 9 15 4 12 9 5 15 10 3 2 5 6 7 8 6 1 6 4 18 6 5 12 12 11 2 10 10 5 10 13 15 13 10 17 7 11 2 1 1 2 1 1 3 2 1 2 17 11 15 3 10 7 15 15 10 5 17 3 3 14 13 11 11 2 3 2 2 3 7 6 1 7 5 3 5 1 7 2 1...
output:
0 2 4 6 7 9 11 16 17 19 28 31 36 41 43 51 55 67 68 0 2 4 6 6 8 10 14 17 18 22 25 0 1 3 5 7 8 11 16 22 26 26 31 33 37 42 42 0 1 3 5 7 9 11 17 19 23 0 1 3 3 4 8 10 12 16 18 27 29 30 34 36 42 46 55 0 0 0 0 1 1 0 2 4 6 9 9 9 11 15 21 27 33 35 38 42 46 55 0 0 3 0 1 3 5 8 10 14 0 1 3 4 6 9 9 0 1 1 3 7 11 ...
result:
ok 6107 lines