# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

661144 | 2022-11-24T16:48:38 Z | amsraman | Arranging Shoes (IOI19_shoes) | C++17 | 43 ms | 10544 KB |

#include <bits/stdc++.h> typedef long long ll; using namespace std; template <typename T> struct FenwickTree { size_t n; vector<T> bit; FenwickTree(size_t n): n(n), bit(n, 0) {}; FenwickTree(vector<T> & init): n((int) init.size()), bit((int) init.size()) { copy(init.begin(), init.end(), bit.begin()); for(int i = 1; i <= n; i++) { if(i + (i & -i) <= n) { bit[i + (i & -i) - 1] += bit[i - 1]; } } } T qry(int k) { T ret = 0; for(k++; k > 0; k -= k & -k) { ret += bit[k - 1]; } return ret; } T qry(int l, int r) { return qry(r) - qry(l - 1); } void upd(int k, T x) { for(k++; k <= n; k += k & -k) { bit[k - 1] += x; } } }; ll count_swaps(vector<int> S) { int n = S.size(); ll ans = 0; FenwickTree<ll> ft(n); vector<int> lefts; vector<vector<int>> rights(n / 2); for(int i = 0; i < n; i++) { ft.upd(i, 1); if(S[i] < 0) { lefts.push_back(i); } else { rights[S[i] - 1].push_back(i); } } for(int i = 0; i < n / 2; i++) { reverse(rights[i].begin(), rights[i].end()); } for(int i = 0; i < n / 2; i++) { ft.upd(lefts[i], -1); ans += ft.qry(lefts[i]); int pos = -S[lefts[i]] - 1, right_back = rights[pos].back(); rights[pos].pop_back(); ft.upd(right_back, -1); ans += ft.qry(right_back); } return ans; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

3 | Correct | 1 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 212 KB | Output is correct |

5 | Correct | 1 ms | 212 KB | Output is correct |

6 | Correct | 1 ms | 304 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 0 ms | 212 KB | Output is correct |

9 | Correct | 1 ms | 296 KB | Output is correct |

10 | Correct | 1 ms | 212 KB | Output is correct |

11 | Correct | 1 ms | 212 KB | Output is correct |

12 | Correct | 1 ms | 212 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Incorrect | 1 ms | 300 KB | Output isn't correct |

15 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

3 | Correct | 1 ms | 212 KB | Output is correct |

4 | Correct | 1 ms | 212 KB | Output is correct |

5 | Correct | 1 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 1 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 212 KB | Output is correct |

9 | Correct | 1 ms | 296 KB | Output is correct |

10 | Correct | 1 ms | 212 KB | Output is correct |

11 | Correct | 1 ms | 212 KB | Output is correct |

12 | Correct | 1 ms | 212 KB | Output is correct |

13 | Correct | 1 ms | 212 KB | Output is correct |

14 | Correct | 0 ms | 212 KB | Output is correct |

15 | Correct | 0 ms | 212 KB | Output is correct |

16 | Correct | 1 ms | 304 KB | Output is correct |

17 | Correct | 0 ms | 212 KB | Output is correct |

18 | Correct | 1 ms | 340 KB | Output is correct |

19 | Correct | 1 ms | 340 KB | Output is correct |

20 | Correct | 4 ms | 1108 KB | Output is correct |

21 | Correct | 3 ms | 1108 KB | Output is correct |

22 | Correct | 34 ms | 7892 KB | Output is correct |

23 | Correct | 31 ms | 7976 KB | Output is correct |

24 | Correct | 34 ms | 7980 KB | Output is correct |

25 | Correct | 28 ms | 7976 KB | Output is correct |

26 | Correct | 32 ms | 7968 KB | Output is correct |

27 | Correct | 30 ms | 7860 KB | Output is correct |

28 | Correct | 30 ms | 8112 KB | Output is correct |

29 | Correct | 31 ms | 8100 KB | Output is correct |

30 | Correct | 32 ms | 8132 KB | Output is correct |

31 | Correct | 34 ms | 7876 KB | Output is correct |

32 | Correct | 29 ms | 8096 KB | Output is correct |

33 | Correct | 31 ms | 7972 KB | Output is correct |

34 | Correct | 34 ms | 8132 KB | Output is correct |

35 | Correct | 1 ms | 212 KB | Output is correct |

36 | Correct | 1 ms | 212 KB | Output is correct |

37 | Correct | 31 ms | 8112 KB | Output is correct |

38 | Correct | 35 ms | 8096 KB | Output is correct |

39 | Correct | 31 ms | 8096 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

3 | Correct | 1 ms | 212 KB | Output is correct |

4 | Correct | 1 ms | 212 KB | Output is correct |

5 | Correct | 43 ms | 10544 KB | Output is correct |

6 | Correct | 43 ms | 8100 KB | Output is correct |

7 | Correct | 41 ms | 10436 KB | Output is correct |

8 | Correct | 33 ms | 8104 KB | Output is correct |

9 | Correct | 40 ms | 10520 KB | Output is correct |

10 | Correct | 43 ms | 8980 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

3 | Correct | 1 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 212 KB | Output is correct |

5 | Correct | 1 ms | 212 KB | Output is correct |

6 | Correct | 1 ms | 304 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 0 ms | 212 KB | Output is correct |

9 | Correct | 1 ms | 296 KB | Output is correct |

10 | Correct | 1 ms | 212 KB | Output is correct |

11 | Correct | 1 ms | 212 KB | Output is correct |

12 | Correct | 1 ms | 212 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Incorrect | 1 ms | 300 KB | Output isn't correct |

15 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 1 ms | 212 KB | Output is correct |

3 | Correct | 1 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 212 KB | Output is correct |

5 | Correct | 1 ms | 212 KB | Output is correct |

6 | Correct | 1 ms | 304 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 0 ms | 212 KB | Output is correct |

9 | Correct | 1 ms | 296 KB | Output is correct |

10 | Correct | 1 ms | 212 KB | Output is correct |

11 | Correct | 1 ms | 212 KB | Output is correct |

12 | Correct | 1 ms | 212 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Incorrect | 1 ms | 300 KB | Output isn't correct |

15 | Halted | 0 ms | 0 KB | - |