Submission #638121

# Submission time Handle Problem Language Result Execution time Memory
638121 2022-09-04T16:38:13 Z JJAnawat Arranging Shoes (IOI19_shoes) C++14
50 / 100
53 ms 27112 KB
#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

bool chk[100005];
vector<int> pl[100005],pr[100005];
int fw[100005];

void up(int x,int v){
    for(int i=x;i<100005;i+=i&-i)
        fw[i]+=v;
}

long long qr(int x){
    long long sum=0;
    for(int i=x;i>0;i-=i&-i)
        sum+=fw[i];
    return sum;
}

long long count_swaps(vector<int> s) {
    int n=s.size();
    for(int i=n-1;i>=0;i--){
        if(s[i]>0)
            pr[s[i]].push_back(i);
        else
            pl[-s[i]].push_back(i);
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        if(chk[i])
            continue;
        int sz=abs(s[i]);
        if(s[i]>0){
            int pos=pl[sz].back();
            chk[pos]=chk[i]=1;
            pl[sz].pop_back();
            pr[sz].pop_back();
            ans+=pos-i-(qr(pos)-qr(i));
            up(pos,1);
        }
        else{
            int pos=pr[sz].back();
            chk[pos]=chk[i]=1;
            pl[sz].pop_back();
            pr[sz].pop_back();
            ans+=pos-i-1-(qr(pos)-qr(i));
            up(pos,1);
        }
    }
    return ans;
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5008 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4972 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 3 ms 5000 KB Output is correct
30 Correct 3 ms 4948 KB Output is correct
31 Correct 4 ms 5000 KB Output is correct
32 Correct 3 ms 5004 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 5000 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5000 KB Output is correct
13 Correct 2 ms 5000 KB Output is correct
14 Correct 3 ms 5000 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 5 ms 5524 KB Output is correct
21 Correct 6 ms 5460 KB Output is correct
22 Runtime error 33 ms 17172 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Runtime error 53 ms 27112 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5008 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4972 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 3 ms 5000 KB Output is correct
30 Correct 3 ms 4948 KB Output is correct
31 Correct 4 ms 5000 KB Output is correct
32 Correct 3 ms 5004 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 5000 KB Output is correct
37 Correct 4 ms 5000 KB Output is correct
38 Correct 4 ms 4948 KB Output is correct
39 Correct 3 ms 4948 KB Output is correct
40 Correct 3 ms 5004 KB Output is correct
41 Correct 3 ms 5076 KB Output is correct
42 Correct 4 ms 5076 KB Output is correct
43 Correct 3 ms 5076 KB Output is correct
44 Correct 3 ms 5080 KB Output is correct
45 Correct 3 ms 5076 KB Output is correct
46 Correct 5 ms 5060 KB Output is correct
47 Correct 3 ms 5032 KB Output is correct
48 Correct 3 ms 5076 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct
50 Correct 3 ms 5012 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 3 ms 5076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5008 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4972 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 3 ms 5000 KB Output is correct
30 Correct 3 ms 4948 KB Output is correct
31 Correct 4 ms 5000 KB Output is correct
32 Correct 3 ms 5004 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 5000 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Correct 3 ms 5004 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 4 ms 5028 KB Output is correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 3 ms 4948 KB Output is correct
46 Correct 3 ms 5000 KB Output is correct
47 Correct 2 ms 5000 KB Output is correct
48 Correct 3 ms 5000 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct
50 Correct 3 ms 4996 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 3 ms 5076 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Correct 5 ms 5524 KB Output is correct
55 Correct 6 ms 5460 KB Output is correct
56 Runtime error 33 ms 17172 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -