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

143481 | 2019-08-14T08:52:56 Z | dolphingarlic | Arranging Shoes (IOI19_shoes) | C++14 | 249 ms | 139032 KB |

#include "shoes.h" #include <queue> int n; long long bit[200001]; std::queue<int> left[100001], right[100001]; void update(int pos) { for (int i = pos; i <= n; i += (i & (-i))) bit[i]++; } long long query(int l, int r) { long long ans = 0; for (int i = r; i > 0; i -= (i & (-i))) ans += bit[i]; for (int i = l; i > 0; i -= (i & (-i))) ans -= bit[i]; return ans; } long long count_swaps(std::vector<int> s) { n = s.size(); for (int i = 0; i < n; i++) { if (s[i] < 0) left[-s[i]].push(i + 1); else right[s[i]].push(i + 1); } long long ans = 0; for (int i = 0; i < n; i++) { if (s[i] < 0) { if (left[-s[i]].front() == i + 1) { int r_indx = right[-s[i]].front(); right[-s[i]].pop(); left[-s[i]].pop(); ans += r_indx - i - 2 - query(i + 1, r_indx); update(r_indx); } } else { if (right[s[i]].front() == i + 1) { int l_indx = left[s[i]].front(); right[s[i]].pop(); left[s[i]].pop(); ans += l_indx - i - 1 - query(i + 1, l_indx); update(l_indx); } } } return ans; }

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

1 | Correct | 139 ms | 134980 KB | Output is correct |

2 | Correct | 136 ms | 134976 KB | Output is correct |

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

1 | Correct | 139 ms | 134980 KB | Output is correct |

2 | Correct | 136 ms | 134976 KB | Output is correct |

3 | Correct | 137 ms | 134924 KB | Output is correct |

4 | Correct | 138 ms | 135028 KB | Output is correct |

5 | Correct | 138 ms | 134948 KB | Output is correct |

6 | Correct | 138 ms | 134880 KB | Output is correct |

7 | Correct | 139 ms | 134904 KB | Output is correct |

8 | Correct | 138 ms | 134908 KB | Output is correct |

9 | Correct | 138 ms | 134940 KB | Output is correct |

10 | Correct | 138 ms | 134932 KB | Output is correct |

11 | Correct | 138 ms | 134904 KB | Output is correct |

12 | Correct | 139 ms | 134956 KB | Output is correct |

13 | Correct | 137 ms | 134904 KB | Output is correct |

14 | Correct | 139 ms | 134952 KB | Output is correct |

15 | Correct | 147 ms | 134880 KB | Output is correct |

16 | Correct | 141 ms | 135076 KB | Output is correct |

17 | Correct | 143 ms | 134912 KB | Output is correct |

18 | Correct | 139 ms | 134876 KB | Output is correct |

19 | Correct | 139 ms | 134904 KB | Output is correct |

20 | Correct | 139 ms | 134884 KB | Output is correct |

21 | Correct | 137 ms | 135032 KB | Output is correct |

22 | Correct | 139 ms | 135120 KB | Output is correct |

23 | Correct | 138 ms | 135036 KB | Output is correct |

24 | Correct | 153 ms | 135032 KB | Output is correct |

25 | Correct | 139 ms | 134924 KB | Output is correct |

26 | Correct | 157 ms | 134992 KB | Output is correct |

27 | Correct | 168 ms | 134956 KB | Output is correct |

28 | Correct | 168 ms | 134988 KB | Output is correct |

29 | Correct | 162 ms | 134972 KB | Output is correct |

30 | Correct | 138 ms | 135032 KB | Output is correct |

31 | Correct | 136 ms | 134904 KB | Output is correct |

32 | Correct | 140 ms | 134904 KB | Output is correct |

33 | Correct | 141 ms | 134904 KB | Output is correct |

34 | Correct | 138 ms | 134904 KB | Output is correct |

35 | Correct | 137 ms | 134988 KB | Output is correct |

36 | Correct | 137 ms | 134904 KB | Output is correct |

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

1 | Correct | 139 ms | 134980 KB | Output is correct |

2 | Correct | 136 ms | 134976 KB | Output is correct |

3 | Correct | 140 ms | 134920 KB | Output is correct |

4 | Correct | 143 ms | 134880 KB | Output is correct |

5 | Correct | 137 ms | 134988 KB | Output is correct |

6 | Correct | 139 ms | 135032 KB | Output is correct |

7 | Correct | 138 ms | 134904 KB | Output is correct |

8 | Correct | 140 ms | 134988 KB | Output is correct |

9 | Correct | 137 ms | 134996 KB | Output is correct |

10 | Correct | 142 ms | 135032 KB | Output is correct |

11 | Correct | 136 ms | 134904 KB | Output is correct |

12 | Correct | 137 ms | 134912 KB | Output is correct |

13 | Correct | 140 ms | 134908 KB | Output is correct |

14 | Correct | 138 ms | 134940 KB | Output is correct |

15 | Correct | 140 ms | 134948 KB | Output is correct |

16 | Correct | 163 ms | 134904 KB | Output is correct |

17 | Correct | 150 ms | 134968 KB | Output is correct |

18 | Correct | 151 ms | 135004 KB | Output is correct |

19 | Correct | 151 ms | 134904 KB | Output is correct |

20 | Correct | 154 ms | 135416 KB | Output is correct |

21 | Correct | 155 ms | 135424 KB | Output is correct |

22 | Correct | 193 ms | 138832 KB | Output is correct |

23 | Correct | 183 ms | 139032 KB | Output is correct |

24 | Correct | 187 ms | 138872 KB | Output is correct |

25 | Correct | 186 ms | 138076 KB | Output is correct |

26 | Correct | 183 ms | 139000 KB | Output is correct |

27 | Correct | 181 ms | 138872 KB | Output is correct |

28 | Correct | 181 ms | 138104 KB | Output is correct |

29 | Correct | 220 ms | 138076 KB | Output is correct |

30 | Correct | 181 ms | 138088 KB | Output is correct |

31 | Correct | 183 ms | 138872 KB | Output is correct |

32 | Correct | 219 ms | 138148 KB | Output is correct |

33 | Correct | 205 ms | 138364 KB | Output is correct |

34 | Correct | 182 ms | 138056 KB | Output is correct |

35 | Correct | 140 ms | 134948 KB | Output is correct |

36 | Correct | 139 ms | 134988 KB | Output is correct |

37 | Correct | 179 ms | 138204 KB | Output is correct |

38 | Correct | 184 ms | 138120 KB | Output is correct |

39 | Correct | 191 ms | 138196 KB | Output is correct |

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

1 | Correct | 138 ms | 134904 KB | Output is correct |

2 | Correct | 139 ms | 134904 KB | Output is correct |

3 | Correct | 146 ms | 134908 KB | Output is correct |

4 | Correct | 164 ms | 134960 KB | Output is correct |

5 | Correct | 234 ms | 137336 KB | Output is correct |

6 | Correct | 198 ms | 137428 KB | Output is correct |

7 | Correct | 249 ms | 137332 KB | Output is correct |

8 | Correct | 182 ms | 138156 KB | Output is correct |

9 | Correct | 233 ms | 137360 KB | Output is correct |

10 | Correct | 220 ms | 137320 KB | Output is correct |

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

1 | Correct | 139 ms | 134980 KB | Output is correct |

2 | Correct | 136 ms | 134976 KB | Output is correct |

3 | Correct | 137 ms | 134924 KB | Output is correct |

4 | Correct | 138 ms | 135028 KB | Output is correct |

5 | Correct | 138 ms | 134948 KB | Output is correct |

6 | Correct | 138 ms | 134880 KB | Output is correct |

7 | Correct | 139 ms | 134904 KB | Output is correct |

8 | Correct | 138 ms | 134908 KB | Output is correct |

9 | Correct | 138 ms | 134940 KB | Output is correct |

10 | Correct | 138 ms | 134932 KB | Output is correct |

11 | Correct | 138 ms | 134904 KB | Output is correct |

12 | Correct | 139 ms | 134956 KB | Output is correct |

13 | Correct | 137 ms | 134904 KB | Output is correct |

14 | Correct | 139 ms | 134952 KB | Output is correct |

15 | Correct | 147 ms | 134880 KB | Output is correct |

16 | Correct | 141 ms | 135076 KB | Output is correct |

17 | Correct | 143 ms | 134912 KB | Output is correct |

18 | Correct | 139 ms | 134876 KB | Output is correct |

19 | Correct | 139 ms | 134904 KB | Output is correct |

20 | Correct | 139 ms | 134884 KB | Output is correct |

21 | Correct | 137 ms | 135032 KB | Output is correct |

22 | Correct | 139 ms | 135120 KB | Output is correct |

23 | Correct | 138 ms | 135036 KB | Output is correct |

24 | Correct | 153 ms | 135032 KB | Output is correct |

25 | Correct | 139 ms | 134924 KB | Output is correct |

26 | Correct | 157 ms | 134992 KB | Output is correct |

27 | Correct | 168 ms | 134956 KB | Output is correct |

28 | Correct | 168 ms | 134988 KB | Output is correct |

29 | Correct | 162 ms | 134972 KB | Output is correct |

30 | Correct | 138 ms | 135032 KB | Output is correct |

31 | Correct | 136 ms | 134904 KB | Output is correct |

32 | Correct | 140 ms | 134904 KB | Output is correct |

33 | Correct | 141 ms | 134904 KB | Output is correct |

34 | Correct | 138 ms | 134904 KB | Output is correct |

35 | Correct | 137 ms | 134988 KB | Output is correct |

36 | Correct | 137 ms | 134904 KB | Output is correct |

37 | Correct | 139 ms | 135016 KB | Output is correct |

38 | Correct | 138 ms | 134888 KB | Output is correct |

39 | Correct | 138 ms | 134996 KB | Output is correct |

40 | Correct | 167 ms | 134860 KB | Output is correct |

41 | Correct | 146 ms | 135116 KB | Output is correct |

42 | Correct | 139 ms | 135072 KB | Output is correct |

43 | Correct | 138 ms | 134852 KB | Output is correct |

44 | Correct | 139 ms | 134904 KB | Output is correct |

45 | Correct | 139 ms | 135004 KB | Output is correct |

46 | Correct | 156 ms | 134904 KB | Output is correct |

47 | Correct | 139 ms | 135004 KB | Output is correct |

48 | Correct | 143 ms | 135032 KB | Output is correct |

49 | Correct | 138 ms | 134932 KB | Output is correct |

50 | Correct | 150 ms | 134948 KB | Output is correct |

51 | Correct | 152 ms | 134976 KB | Output is correct |

52 | Correct | 143 ms | 134892 KB | Output is correct |

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

1 | Correct | 139 ms | 134980 KB | Output is correct |

2 | Correct | 136 ms | 134976 KB | Output is correct |

3 | Correct | 137 ms | 134924 KB | Output is correct |

4 | Correct | 138 ms | 135028 KB | Output is correct |

5 | Correct | 138 ms | 134948 KB | Output is correct |

6 | Correct | 138 ms | 134880 KB | Output is correct |

7 | Correct | 139 ms | 134904 KB | Output is correct |

8 | Correct | 138 ms | 134908 KB | Output is correct |

9 | Correct | 138 ms | 134940 KB | Output is correct |

10 | Correct | 138 ms | 134932 KB | Output is correct |

11 | Correct | 138 ms | 134904 KB | Output is correct |

12 | Correct | 139 ms | 134956 KB | Output is correct |

13 | Correct | 137 ms | 134904 KB | Output is correct |

14 | Correct | 139 ms | 134952 KB | Output is correct |

15 | Correct | 147 ms | 134880 KB | Output is correct |

16 | Correct | 141 ms | 135076 KB | Output is correct |

17 | Correct | 143 ms | 134912 KB | Output is correct |

18 | Correct | 139 ms | 134876 KB | Output is correct |

19 | Correct | 139 ms | 134904 KB | Output is correct |

20 | Correct | 139 ms | 134884 KB | Output is correct |

21 | Correct | 137 ms | 135032 KB | Output is correct |

22 | Correct | 139 ms | 135120 KB | Output is correct |

23 | Correct | 138 ms | 135036 KB | Output is correct |

24 | Correct | 153 ms | 135032 KB | Output is correct |

25 | Correct | 139 ms | 134924 KB | Output is correct |

26 | Correct | 157 ms | 134992 KB | Output is correct |

27 | Correct | 168 ms | 134956 KB | Output is correct |

28 | Correct | 168 ms | 134988 KB | Output is correct |

29 | Correct | 162 ms | 134972 KB | Output is correct |

30 | Correct | 138 ms | 135032 KB | Output is correct |

31 | Correct | 136 ms | 134904 KB | Output is correct |

32 | Correct | 140 ms | 134904 KB | Output is correct |

33 | Correct | 141 ms | 134904 KB | Output is correct |

34 | Correct | 138 ms | 134904 KB | Output is correct |

35 | Correct | 137 ms | 134988 KB | Output is correct |

36 | Correct | 137 ms | 134904 KB | Output is correct |

37 | Correct | 140 ms | 134920 KB | Output is correct |

38 | Correct | 143 ms | 134880 KB | Output is correct |

39 | Correct | 137 ms | 134988 KB | Output is correct |

40 | Correct | 139 ms | 135032 KB | Output is correct |

41 | Correct | 138 ms | 134904 KB | Output is correct |

42 | Correct | 140 ms | 134988 KB | Output is correct |

43 | Correct | 137 ms | 134996 KB | Output is correct |

44 | Correct | 142 ms | 135032 KB | Output is correct |

45 | Correct | 136 ms | 134904 KB | Output is correct |

46 | Correct | 137 ms | 134912 KB | Output is correct |

47 | Correct | 140 ms | 134908 KB | Output is correct |

48 | Correct | 138 ms | 134940 KB | Output is correct |

49 | Correct | 140 ms | 134948 KB | Output is correct |

50 | Correct | 163 ms | 134904 KB | Output is correct |

51 | Correct | 150 ms | 134968 KB | Output is correct |

52 | Correct | 151 ms | 135004 KB | Output is correct |

53 | Correct | 151 ms | 134904 KB | Output is correct |

54 | Correct | 154 ms | 135416 KB | Output is correct |

55 | Correct | 155 ms | 135424 KB | Output is correct |

56 | Correct | 193 ms | 138832 KB | Output is correct |

57 | Correct | 183 ms | 139032 KB | Output is correct |

58 | Correct | 187 ms | 138872 KB | Output is correct |

59 | Correct | 186 ms | 138076 KB | Output is correct |

60 | Correct | 183 ms | 139000 KB | Output is correct |

61 | Correct | 181 ms | 138872 KB | Output is correct |

62 | Correct | 181 ms | 138104 KB | Output is correct |

63 | Correct | 220 ms | 138076 KB | Output is correct |

64 | Correct | 181 ms | 138088 KB | Output is correct |

65 | Correct | 183 ms | 138872 KB | Output is correct |

66 | Correct | 219 ms | 138148 KB | Output is correct |

67 | Correct | 205 ms | 138364 KB | Output is correct |

68 | Correct | 182 ms | 138056 KB | Output is correct |

69 | Correct | 140 ms | 134948 KB | Output is correct |

70 | Correct | 139 ms | 134988 KB | Output is correct |

71 | Correct | 179 ms | 138204 KB | Output is correct |

72 | Correct | 184 ms | 138120 KB | Output is correct |

73 | Correct | 191 ms | 138196 KB | Output is correct |

74 | Correct | 138 ms | 134904 KB | Output is correct |

75 | Correct | 139 ms | 134904 KB | Output is correct |

76 | Correct | 146 ms | 134908 KB | Output is correct |

77 | Correct | 164 ms | 134960 KB | Output is correct |

78 | Correct | 234 ms | 137336 KB | Output is correct |

79 | Correct | 198 ms | 137428 KB | Output is correct |

80 | Correct | 249 ms | 137332 KB | Output is correct |

81 | Correct | 182 ms | 138156 KB | Output is correct |

82 | Correct | 233 ms | 137360 KB | Output is correct |

83 | Correct | 220 ms | 137320 KB | Output is correct |

84 | Correct | 139 ms | 135016 KB | Output is correct |

85 | Correct | 138 ms | 134888 KB | Output is correct |

86 | Correct | 138 ms | 134996 KB | Output is correct |

87 | Correct | 167 ms | 134860 KB | Output is correct |

88 | Correct | 146 ms | 135116 KB | Output is correct |

89 | Correct | 139 ms | 135072 KB | Output is correct |

90 | Correct | 138 ms | 134852 KB | Output is correct |

91 | Correct | 139 ms | 134904 KB | Output is correct |

92 | Correct | 139 ms | 135004 KB | Output is correct |

93 | Correct | 156 ms | 134904 KB | Output is correct |

94 | Correct | 139 ms | 135004 KB | Output is correct |

95 | Correct | 143 ms | 135032 KB | Output is correct |

96 | Correct | 138 ms | 134932 KB | Output is correct |

97 | Correct | 150 ms | 134948 KB | Output is correct |

98 | Correct | 152 ms | 134976 KB | Output is correct |

99 | Correct | 143 ms | 134892 KB | Output is correct |

100 | Correct | 148 ms | 135036 KB | Output is correct |

101 | Correct | 148 ms | 135288 KB | Output is correct |

102 | Correct | 144 ms | 135296 KB | Output is correct |

103 | Correct | 246 ms | 138248 KB | Output is correct |

104 | Correct | 230 ms | 138104 KB | Output is correct |

105 | Correct | 234 ms | 138104 KB | Output is correct |

106 | Correct | 235 ms | 137464 KB | Output is correct |

107 | Correct | 203 ms | 138104 KB | Output is correct |

108 | Correct | 208 ms | 138076 KB | Output is correct |

109 | Correct | 177 ms | 138232 KB | Output is correct |

110 | Correct | 180 ms | 138104 KB | Output is correct |

111 | Correct | 228 ms | 137388 KB | Output is correct |

112 | Correct | 237 ms | 138232 KB | Output is correct |

113 | Correct | 209 ms | 137464 KB | Output is correct |

114 | Correct | 232 ms | 137432 KB | Output is correct |

115 | Correct | 243 ms | 137336 KB | Output is correct |