QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#577741	#9327. Permutation and Queries	Afterlife^#	RE	1ms	3792kb	C++20	2.5kb	2024-09-20 14:28:27	2024-09-20 14:28:28

Judging History

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

[2024-09-20 14:28:28]
评测

测评结果：RE
用时：1ms
内存：3792kb

查看

[2024-09-20 14:28:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
struct mt {
    int p[100005] , B;
    priority_queue<int , vector<int> , greater<int> > pq[320] , dec[320];
    void init() {
        B = sqrt(n);
        for(int i = 1;i <= n;i++) {
            for(int j = i + 1 ; j <= i + B && j <= n;j++) {
                if(1LL * (j - i) * abs(p[i] - p[j]) >= n) continue ;
                pq[j - i].push(abs(p[i] - p[j]));
            }
        }
    }
    int calc() {
        int ans = 1e9;
        for(int i = 1;i <= B;i++) {
            while(dec[i].size() && pq[i].top() == dec[i].top()) {
                pq[i].pop() ; dec[i].pop() ;
            }
            int mn = pq[i].top() ;
            if(1LL * i* mn < ans) ans = i * mn;
        }
        return ans;
    }
    void swp(int a,int b) {
        if(a > b) swap(a,b) ;
        for(int i = max(1 , a - B) ; i <= a + B && i <= n;i++) {
            if(i == a) continue ;
            if(1LL * abs(p[i] - p[a]) * abs(i - a) >= n) continue ;
            dec[abs(i - a)].push(abs(p[i] - p[a]));
        }
        for(int i = max(1 , b - B) ; i <= b + B && i <= n;i++) {
            if(i == b) continue ;
            if(i == a) continue ;
            if(1LL * abs(p[i] - p[b]) * abs(i - b) >= n) continue ;
            dec [abs(i - b)].push(abs(p[i] - p[b])) ;
        }

        swap(p[a] , p[b]) ;
        for(int i = max(1 , a - B) ; i <= a + B && i <= n;i++) {
            if(i == a) continue ;
            if(1LL * abs(p[i] - p[a]) * abs(i - a) >= n) continue ;
            pq[abs(i - a)].push(abs(p[i] - p[a]));
        }
        for(int i = max(1 , b - B) ; i <= b + B && i <= n;i++) {
            if(i == b) continue ;
            if(i == a) continue ;
            if(1LL * abs(p[i] - p[b]) * abs(i - b) >= n) continue ;
            pq [abs(i - b)].push(abs(p[i] - p[b])) ;
        }
        return ;
    }
}p , r;
int q;
int val[100005];
void solv() {
    cin >> n >> q;
    for(int i = 1;i <= n;i++) {
        cin >> p.p[i];
        val[i] = p.p[i];
        r.p[p.p[i]] = i;
    }
    p.init() ; r.init() ;
    cout << min(p.calc() , r.calc()) << '\n' ;
    for(int i = 1;i <= q;i++) {
        int a , b;
        cin >> a >> b;
        p.swp(a,b) ;
        r.swp(val[a] ,val[b]);
        swap(val[a] , val[b]) ;
        cout << min(p.calc() , r.calc()) << '\n' ;
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int t = 1;
    while(t--) solv() ;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3744kb

input:

6 5
2 4 1 6 3 5
1 2
3 5
1 2
5 3
5 6

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

10 20
1 4 7 10 2 5 8 3 6 9
10 1
5 7
1 2
5 3
6 3
9 4
3 4
9 6
8 4
9 6
8 7
3 8
10 7
2 7
3 7
5 9
7 6
4 6
2 10
8 9

output:

result:

ok 21 numbers

Test #3:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok 7 numbers

Test #4:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok 5 number(s): "1 1 1 1 1"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3784kb

input:

output:

result:

ok 6 numbers

Test #6:

score: -100

Runtime Error

input:

100 1000
1 11 21 31 41 51 61 71 81 91 2 12 22 32 42 52 62 72 82 92 3 13 23 33 43 53 63 73 83 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6 16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 19 29 39 49 59 69 79 89 99 10 20 30 40 50 60 70 80 90 100...