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

143472 | 2019-08-14T08:24:52 Z | mat_v | Arranging Shoes (IOI19_shoes) | C++14 | 203 ms | 22648 KB |

#include "shoes.h" #include <bits/stdc++.h> #include <cstdio> #include <cassert> #define pb push_back using namespace std; int n; vector<int> tike[200005][2]; int dokle[200005][2]; int seg[600005]; int lazy[600005]; bool bio[200005]; void init(int l, int r, int ind){ if(l == r){ seg[ind] = l; return; } int mid = (l + r) / 2; init(l, mid, ind * 2); init(mid + 1, r, ind * 2 + 1); seg[ind] = seg[ind * 2] + seg[ind * 2 + 1]; } void propagate(int l, int r, int ind){ if(lazy[ind] != 0){ seg[ind] += (r - l + 1)*lazy[ind]; int mid = (l + r) / 2; if(l < r){ lazy[ind * 2] += lazy[ind]; lazy[ind * 2 + 1] += lazy[ind]; } lazy[ind] = 0; } } int query(int l,int r, int ind, int gde){ propagate(l,r,ind); if(l == r)return seg[ind]; int mid = (l + r)/2; if(gde <= mid)return query(l,mid,ind * 2, gde); else return query(mid + 1, r, ind * 2 + 1, gde); } void update(int l, int r, int ind, int levo, int desno, int val){ propagate(l,r,ind); if(l >= levo && r <= desno){ lazy[ind]+=val; propagate(l,r,ind); return; } if(desno < l || r < levo)return; int mid = (l + r) / 2; update(l,mid,ind * 2,levo,desno,val); update(mid + 1,r,ind * 2 + 1,levo,desno,val); propagate(l,mid,ind*2); propagate(mid+1,r,ind*2+1); seg[ind] = seg[ind*2] + seg[ind*2+1]; propagate(l,r,ind); } long long count_swaps(std::vector<int> s) { n = s.size()/2; for(int i=0; i<2*n; i++){ if(s[i] < 0)tike[abs(s[i])][0].pb(i); else tike[s[i]][1].pb(i); } int l = 0; int shift = 0; init(0,2*n-1,1); long long res = 0; for(int i=0; i<n; i++){ while(bio[l])++l; int koji = abs(s[l]); int ind; if(s[l] < 0)ind = 1; else ind = 0; int gde = tike[koji][ind][dokle[koji][ind]]; bio[gde] = 1; dokle[koji][ind]++; dokle[koji][ind^1]++; int pom = query(0,2*n-1,1,gde); //cout << pom << " " << gde << endl; update(0,2*n-1,1,0,gde - 1,1); //bio[l + 1] = 1; res += (pom - 2*(i) - 1); res += 1-ind; l ++; } return res; }

### Compilation message

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

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

2 | Correct | 10 ms | 9720 KB | Output is correct |

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

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

2 | Correct | 10 ms | 9720 KB | Output is correct |

3 | Correct | 11 ms | 9720 KB | Output is correct |

4 | Correct | 11 ms | 9720 KB | Output is correct |

5 | Correct | 10 ms | 9720 KB | Output is correct |

6 | Correct | 10 ms | 9720 KB | Output is correct |

7 | Correct | 10 ms | 9720 KB | Output is correct |

8 | Correct | 11 ms | 9720 KB | Output is correct |

9 | Correct | 10 ms | 9720 KB | Output is correct |

10 | Correct | 13 ms | 9720 KB | Output is correct |

11 | Correct | 13 ms | 9720 KB | Output is correct |

12 | Correct | 11 ms | 9724 KB | Output is correct |

13 | Correct | 10 ms | 9720 KB | Output is correct |

14 | Correct | 10 ms | 9724 KB | Output is correct |

15 | Correct | 10 ms | 9720 KB | Output is correct |

16 | Correct | 11 ms | 9720 KB | Output is correct |

17 | Correct | 10 ms | 9720 KB | Output is correct |

18 | Correct | 10 ms | 9720 KB | Output is correct |

19 | Correct | 11 ms | 9720 KB | Output is correct |

20 | Correct | 10 ms | 9720 KB | Output is correct |

21 | Correct | 11 ms | 9720 KB | Output is correct |

22 | Correct | 11 ms | 9720 KB | Output is correct |

23 | Correct | 11 ms | 9720 KB | Output is correct |

24 | Correct | 10 ms | 9720 KB | Output is correct |

25 | Correct | 11 ms | 9720 KB | Output is correct |

26 | Correct | 11 ms | 9720 KB | Output is correct |

27 | Correct | 11 ms | 9720 KB | Output is correct |

28 | Correct | 11 ms | 9720 KB | Output is correct |

29 | Correct | 10 ms | 9720 KB | Output is correct |

30 | Correct | 10 ms | 9720 KB | Output is correct |

31 | Correct | 10 ms | 9720 KB | Output is correct |

32 | Correct | 11 ms | 9720 KB | Output is correct |

33 | Correct | 11 ms | 9748 KB | Output is correct |

34 | Correct | 10 ms | 9720 KB | Output is correct |

35 | Correct | 11 ms | 9720 KB | Output is correct |

36 | Correct | 10 ms | 9692 KB | Output is correct |

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

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

2 | Correct | 10 ms | 9720 KB | Output is correct |

3 | Correct | 10 ms | 9720 KB | Output is correct |

4 | Correct | 11 ms | 9720 KB | Output is correct |

5 | Correct | 11 ms | 9720 KB | Output is correct |

6 | Correct | 11 ms | 9720 KB | Output is correct |

7 | Correct | 13 ms | 9720 KB | Output is correct |

8 | Correct | 11 ms | 9848 KB | Output is correct |

9 | Correct | 10 ms | 9720 KB | Output is correct |

10 | Correct | 10 ms | 9720 KB | Output is correct |

11 | Correct | 10 ms | 9720 KB | Output is correct |

12 | Correct | 10 ms | 9720 KB | Output is correct |

13 | Correct | 10 ms | 9724 KB | Output is correct |

14 | Correct | 10 ms | 9720 KB | Output is correct |

15 | Correct | 13 ms | 9720 KB | Output is correct |

16 | Correct | 10 ms | 9692 KB | Output is correct |

17 | Correct | 11 ms | 9720 KB | Output is correct |

18 | Correct | 11 ms | 9720 KB | Output is correct |

19 | Correct | 11 ms | 9720 KB | Output is correct |

20 | Correct | 19 ms | 10588 KB | Output is correct |

21 | Correct | 22 ms | 10628 KB | Output is correct |

22 | Correct | 107 ms | 16480 KB | Output is correct |

23 | Correct | 97 ms | 16620 KB | Output is correct |

24 | Correct | 103 ms | 16580 KB | Output is correct |

25 | Correct | 95 ms | 15460 KB | Output is correct |

26 | Correct | 102 ms | 16620 KB | Output is correct |

27 | Correct | 105 ms | 16620 KB | Output is correct |

28 | Correct | 98 ms | 15468 KB | Output is correct |

29 | Correct | 101 ms | 15472 KB | Output is correct |

30 | Correct | 104 ms | 15464 KB | Output is correct |

31 | Correct | 104 ms | 16456 KB | Output is correct |

32 | Correct | 96 ms | 15608 KB | Output is correct |

33 | Correct | 99 ms | 15444 KB | Output is correct |

34 | Correct | 96 ms | 15468 KB | Output is correct |

35 | Correct | 16 ms | 9720 KB | Output is correct |

36 | Correct | 13 ms | 9720 KB | Output is correct |

37 | Correct | 98 ms | 15444 KB | Output is correct |

38 | Correct | 103 ms | 15440 KB | Output is correct |

39 | Correct | 109 ms | 15480 KB | Output is correct |

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

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

2 | Correct | 10 ms | 9768 KB | Output is correct |

3 | Correct | 11 ms | 9832 KB | Output is correct |

4 | Correct | 11 ms | 9720 KB | Output is correct |

5 | Correct | 156 ms | 21488 KB | Output is correct |

6 | Correct | 128 ms | 16760 KB | Output is correct |

7 | Correct | 156 ms | 21544 KB | Output is correct |

8 | Correct | 100 ms | 15416 KB | Output is correct |

9 | Correct | 156 ms | 21516 KB | Output is correct |

10 | Correct | 155 ms | 18552 KB | Output is correct |

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

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

2 | Correct | 10 ms | 9720 KB | Output is correct |

3 | Correct | 11 ms | 9720 KB | Output is correct |

4 | Correct | 11 ms | 9720 KB | Output is correct |

5 | Correct | 10 ms | 9720 KB | Output is correct |

6 | Correct | 10 ms | 9720 KB | Output is correct |

7 | Correct | 10 ms | 9720 KB | Output is correct |

8 | Correct | 11 ms | 9720 KB | Output is correct |

9 | Correct | 10 ms | 9720 KB | Output is correct |

10 | Correct | 13 ms | 9720 KB | Output is correct |

11 | Correct | 13 ms | 9720 KB | Output is correct |

12 | Correct | 11 ms | 9724 KB | Output is correct |

13 | Correct | 10 ms | 9720 KB | Output is correct |

14 | Correct | 10 ms | 9724 KB | Output is correct |

15 | Correct | 10 ms | 9720 KB | Output is correct |

16 | Correct | 11 ms | 9720 KB | Output is correct |

17 | Correct | 10 ms | 9720 KB | Output is correct |

18 | Correct | 10 ms | 9720 KB | Output is correct |

19 | Correct | 11 ms | 9720 KB | Output is correct |

20 | Correct | 10 ms | 9720 KB | Output is correct |

21 | Correct | 11 ms | 9720 KB | Output is correct |

22 | Correct | 11 ms | 9720 KB | Output is correct |

23 | Correct | 11 ms | 9720 KB | Output is correct |

24 | Correct | 10 ms | 9720 KB | Output is correct |

25 | Correct | 11 ms | 9720 KB | Output is correct |

26 | Correct | 11 ms | 9720 KB | Output is correct |

27 | Correct | 11 ms | 9720 KB | Output is correct |

28 | Correct | 11 ms | 9720 KB | Output is correct |

29 | Correct | 10 ms | 9720 KB | Output is correct |

30 | Correct | 10 ms | 9720 KB | Output is correct |

31 | Correct | 10 ms | 9720 KB | Output is correct |

32 | Correct | 11 ms | 9720 KB | Output is correct |

33 | Correct | 11 ms | 9748 KB | Output is correct |

34 | Correct | 10 ms | 9720 KB | Output is correct |

35 | Correct | 11 ms | 9720 KB | Output is correct |

36 | Correct | 10 ms | 9692 KB | Output is correct |

37 | Correct | 10 ms | 9720 KB | Output is correct |

38 | Correct | 10 ms | 9720 KB | Output is correct |

39 | Correct | 11 ms | 9720 KB | Output is correct |

40 | Correct | 11 ms | 9720 KB | Output is correct |

41 | Correct | 12 ms | 9848 KB | Output is correct |

42 | Correct | 11 ms | 9848 KB | Output is correct |

43 | Correct | 11 ms | 9848 KB | Output is correct |

44 | Correct | 12 ms | 9848 KB | Output is correct |

45 | Correct | 12 ms | 9848 KB | Output is correct |

46 | Correct | 12 ms | 9848 KB | Output is correct |

47 | Correct | 15 ms | 9848 KB | Output is correct |

48 | Correct | 12 ms | 9848 KB | Output is correct |

49 | Correct | 12 ms | 9848 KB | Output is correct |

50 | Correct | 11 ms | 9848 KB | Output is correct |

51 | Correct | 11 ms | 9720 KB | Output is correct |

52 | Correct | 11 ms | 9848 KB | Output is correct |

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

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

2 | Correct | 10 ms | 9720 KB | Output is correct |

3 | Correct | 11 ms | 9720 KB | Output is correct |

4 | Correct | 11 ms | 9720 KB | Output is correct |

5 | Correct | 10 ms | 9720 KB | Output is correct |

6 | Correct | 10 ms | 9720 KB | Output is correct |

7 | Correct | 10 ms | 9720 KB | Output is correct |

8 | Correct | 11 ms | 9720 KB | Output is correct |

9 | Correct | 10 ms | 9720 KB | Output is correct |

10 | Correct | 13 ms | 9720 KB | Output is correct |

11 | Correct | 13 ms | 9720 KB | Output is correct |

12 | Correct | 11 ms | 9724 KB | Output is correct |

13 | Correct | 10 ms | 9720 KB | Output is correct |

14 | Correct | 10 ms | 9724 KB | Output is correct |

15 | Correct | 10 ms | 9720 KB | Output is correct |

16 | Correct | 11 ms | 9720 KB | Output is correct |

17 | Correct | 10 ms | 9720 KB | Output is correct |

18 | Correct | 10 ms | 9720 KB | Output is correct |

19 | Correct | 11 ms | 9720 KB | Output is correct |

20 | Correct | 10 ms | 9720 KB | Output is correct |

21 | Correct | 11 ms | 9720 KB | Output is correct |

22 | Correct | 11 ms | 9720 KB | Output is correct |

23 | Correct | 11 ms | 9720 KB | Output is correct |

24 | Correct | 10 ms | 9720 KB | Output is correct |

25 | Correct | 11 ms | 9720 KB | Output is correct |

26 | Correct | 11 ms | 9720 KB | Output is correct |

27 | Correct | 11 ms | 9720 KB | Output is correct |

28 | Correct | 11 ms | 9720 KB | Output is correct |

29 | Correct | 10 ms | 9720 KB | Output is correct |

30 | Correct | 10 ms | 9720 KB | Output is correct |

31 | Correct | 10 ms | 9720 KB | Output is correct |

32 | Correct | 11 ms | 9720 KB | Output is correct |

33 | Correct | 11 ms | 9748 KB | Output is correct |

34 | Correct | 10 ms | 9720 KB | Output is correct |

35 | Correct | 11 ms | 9720 KB | Output is correct |

36 | Correct | 10 ms | 9692 KB | Output is correct |

37 | Correct | 10 ms | 9720 KB | Output is correct |

38 | Correct | 11 ms | 9720 KB | Output is correct |

39 | Correct | 11 ms | 9720 KB | Output is correct |

40 | Correct | 11 ms | 9720 KB | Output is correct |

41 | Correct | 13 ms | 9720 KB | Output is correct |

42 | Correct | 11 ms | 9848 KB | Output is correct |

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

44 | Correct | 10 ms | 9720 KB | Output is correct |

45 | Correct | 10 ms | 9720 KB | Output is correct |

46 | Correct | 10 ms | 9720 KB | Output is correct |

47 | Correct | 10 ms | 9724 KB | Output is correct |

48 | Correct | 10 ms | 9720 KB | Output is correct |

49 | Correct | 13 ms | 9720 KB | Output is correct |

50 | Correct | 10 ms | 9692 KB | Output is correct |

51 | Correct | 11 ms | 9720 KB | Output is correct |

52 | Correct | 11 ms | 9720 KB | Output is correct |

53 | Correct | 11 ms | 9720 KB | Output is correct |

54 | Correct | 19 ms | 10588 KB | Output is correct |

55 | Correct | 22 ms | 10628 KB | Output is correct |

56 | Correct | 107 ms | 16480 KB | Output is correct |

57 | Correct | 97 ms | 16620 KB | Output is correct |

58 | Correct | 103 ms | 16580 KB | Output is correct |

59 | Correct | 95 ms | 15460 KB | Output is correct |

60 | Correct | 102 ms | 16620 KB | Output is correct |

61 | Correct | 105 ms | 16620 KB | Output is correct |

62 | Correct | 98 ms | 15468 KB | Output is correct |

63 | Correct | 101 ms | 15472 KB | Output is correct |

64 | Correct | 104 ms | 15464 KB | Output is correct |

65 | Correct | 104 ms | 16456 KB | Output is correct |

66 | Correct | 96 ms | 15608 KB | Output is correct |

67 | Correct | 99 ms | 15444 KB | Output is correct |

68 | Correct | 96 ms | 15468 KB | Output is correct |

69 | Correct | 16 ms | 9720 KB | Output is correct |

70 | Correct | 13 ms | 9720 KB | Output is correct |

71 | Correct | 98 ms | 15444 KB | Output is correct |

72 | Correct | 103 ms | 15440 KB | Output is correct |

73 | Correct | 109 ms | 15480 KB | Output is correct |

74 | Correct | 13 ms | 9720 KB | Output is correct |

75 | Correct | 10 ms | 9768 KB | Output is correct |

76 | Correct | 11 ms | 9832 KB | Output is correct |

77 | Correct | 11 ms | 9720 KB | Output is correct |

78 | Correct | 156 ms | 21488 KB | Output is correct |

79 | Correct | 128 ms | 16760 KB | Output is correct |

80 | Correct | 156 ms | 21544 KB | Output is correct |

81 | Correct | 100 ms | 15416 KB | Output is correct |

82 | Correct | 156 ms | 21516 KB | Output is correct |

83 | Correct | 155 ms | 18552 KB | Output is correct |

84 | Correct | 10 ms | 9720 KB | Output is correct |

85 | Correct | 10 ms | 9720 KB | Output is correct |

86 | Correct | 11 ms | 9720 KB | Output is correct |

87 | Correct | 11 ms | 9720 KB | Output is correct |

88 | Correct | 12 ms | 9848 KB | Output is correct |

89 | Correct | 11 ms | 9848 KB | Output is correct |

90 | Correct | 11 ms | 9848 KB | Output is correct |

91 | Correct | 12 ms | 9848 KB | Output is correct |

92 | Correct | 12 ms | 9848 KB | Output is correct |

93 | Correct | 12 ms | 9848 KB | Output is correct |

94 | Correct | 15 ms | 9848 KB | Output is correct |

95 | Correct | 12 ms | 9848 KB | Output is correct |

96 | Correct | 12 ms | 9848 KB | Output is correct |

97 | Correct | 11 ms | 9848 KB | Output is correct |

98 | Correct | 11 ms | 9720 KB | Output is correct |

99 | Correct | 11 ms | 9848 KB | Output is correct |

100 | Correct | 12 ms | 9848 KB | Output is correct |

101 | Correct | 24 ms | 11132 KB | Output is correct |

102 | Correct | 23 ms | 10744 KB | Output is correct |

103 | Correct | 203 ms | 22648 KB | Output is correct |

104 | Correct | 148 ms | 22648 KB | Output is correct |

105 | Correct | 175 ms | 19912 KB | Output is correct |

106 | Correct | 154 ms | 21624 KB | Output is correct |

107 | Correct | 142 ms | 17996 KB | Output is correct |

108 | Correct | 142 ms | 18296 KB | Output is correct |

109 | Correct | 100 ms | 15732 KB | Output is correct |

110 | Correct | 96 ms | 15484 KB | Output is correct |

111 | Correct | 154 ms | 20856 KB | Output is correct |

112 | Correct | 182 ms | 21332 KB | Output is correct |

113 | Correct | 163 ms | 16964 KB | Output is correct |

114 | Correct | 152 ms | 21496 KB | Output is correct |

115 | Correct | 151 ms | 21576 KB | Output is correct |