为什么在洛谷上AC,但是其他OI全RE?

P1908 逆序对

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 额确实是离散化,我瞎了。。。
不过你这玩意没去重,假设输入 a_i 里面有重复数字你就寄了。


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

Judging 评测:编译成功,正在评测中

Accepted 通过:程序输出完全正确


上一页 | 下一页