NirvanaCeleste @ 2024-07-11 07:03:15
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500100;
long long tree[MAXN],ranks[MAXN];
long long ans,n;
struct point {
long long num,val;
} a[MAXN];
bool cmp(point q,point w) {
if(q.val == w.val) return q.num < w.num;
return q.val < w.val;
}
void add(int p,long d) {
for(; p<=n; p += p & (-p)) tree[p] += d;
}
long long sum(int p) {
long long pll = 0;
for(; p; p -= p & (-p)) pll += tree[p];
return pll;
}
int main() {
scanf("%lld\n",&n);
for(int i=1; i<=n; i++){
scanf("%lld\n",&a[i].val);
a[i].num = i;
}
sort(a+1,a+1+n,cmp);
for(int i=1; i<=n; i++) ranks[a[i].num] = i;
for(int i=n; i>=1; i--) {
ans += sum(ranks[i] - 1);
add(ranks[i],1);
}
printf("%lld\n",ans);
return 0;
}
by NirvanaCeleste @ 2024-07-11 07:56:03
@Lyw_Cyq_01 好的。 但是ranks[]是不是已经使用了离散化了? 他的下标和n有关。
by FiraCode @ 2024-07-11 07:58:04
@Lyw_Cyq_01 1≤n,ai≤10^5
by Lyw_and_Segment_Tree @ 2024-07-11 08:06:10
@NirvanaCeleste 额确实是离散化,我瞎了。。。
不过你这玩意没去重,假设输入
by Duce_X @ 2024-07-11 08:24:11
@NirvanaCeleste
OI只有一个,评测平台叫 OJ(Online Judge)
(擦汗)
by FiraCode @ 2024-07-11 09:52:52
@NirvanaCeleste @Lyw_Cyq_01 破案了。
scanf("%lld\n",&a[i].val);
by NirvanaCeleste @ 2024-07-11 10:11:27
@FiraCode 全RE http://172.20.0.170/d/summer/record/668f3f211572626289fcafcf
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500050;
long long tre[MAXN],ranks[MAXN];
long long ans;
int n;
struct point {
long long num,val;
} a[MAXN];
bool cmp(point q,point w) {
if(q.val == w.val) return q.num < w.num;
return q.val < w.val;
}
void add(int p,long long d) {
for(; p<=n; p += p & (-p)) tre[p] += d;
return;
}
long long count(int p) {
long long t = 0;
for(; p; p -= p & (-p)) t += tre[p];
return t;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%lld",&a[i].val);
a[i].num = i;
}
sort(a+1,a+1+n,cmp);
for(int i=1; i<=n; i++) ranks[a[i].num] = i;
for(int i=n; i>=1; i--) {
ans += count(ranks[i] - 1);
add(ranks[i],1);
}
printf("%lld",ans);
return 0;
}
by NirvanaCeleste @ 2024-07-11 10:14:05
@FiraCode 同样的,改成cin也不行
by NirvanaCeleste @ 2024-07-11 10:19:01
@FiraCode 可能是测评有问题。这个也会全部RE。
#include <bits/stdc++.h>
using namespace std;
int main(){
cout<<1;
return 0;
}
by FiraCode @ 2024-07-11 11:06:04
@NirvanaCeleste 有可能是WA显示RE(
您试试改一改。
by Kete @ 2024-07-11 11:50:40
Waiting 评测:评测请求正在等待被评测机抓取
Fetched 评测:评测请求已被评测机抓取,正在准备开始评测
Compiling 评测:正在编译中
Judging 评测:编译成功,正在评测中
Accepted 通过:程序输出完全正确
Wrong Answer 不通过:程序输出与标准答案不一致(不包括行末空格以及文件末空行)
Time Limit Exceeded 不通过:程序运行时间超过了题目限制
Memory Limit Exceeded 不通过:程序运行内存空间超过了题目限制
Runtime Error 不通过:程序运行时错误(如数组越界、被零除、运算溢出、栈溢出、无效指针等)
希望能给你们带来一些帮助