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

143467 | 2019-08-14T08:17:40 Z | mat_v | Arranging Shoes (IOI19_shoes) | C++14 | 94 ms | 29276 KB |

#include "shoes.h" #include <bits/stdc++.h> #include <cstdio> #include <cassert> #define pb push_back using namespace std; int n; vector<int> tike[100005][2]; int dokle[100005][2]; int seg[200005]; int lazy[200005]; 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); //bio[l + 1] = 1; res += (pom - 2*(i) - 1); res += 1-ind; //cout << l << " " << pom << " " << gde << endl; //cout << l << " " << res << " " << ind<< endl; l ++; // cout << endl; //cout << query(0,2*n-1,1,0) << endl;; // return 0; } return res; }

### Compilation message

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

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

2 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

2 | Correct | 6 ms | 5112 KB | Output is correct |

3 | Correct | 6 ms | 4984 KB | Output is correct |

4 | Correct | 6 ms | 4984 KB | Output is correct |

5 | Correct | 6 ms | 4984 KB | Output is correct |

6 | Correct | 6 ms | 4984 KB | Output is correct |

7 | Correct | 6 ms | 5112 KB | Output is correct |

8 | Correct | 6 ms | 4984 KB | Output is correct |

9 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

12 | Correct | 6 ms | 5112 KB | Output is correct |

13 | Correct | 6 ms | 4984 KB | Output is correct |

14 | Correct | 6 ms | 4984 KB | Output is correct |

15 | Correct | 6 ms | 4956 KB | Output is correct |

16 | Correct | 6 ms | 4984 KB | Output is correct |

17 | Correct | 6 ms | 4984 KB | Output is correct |

18 | Correct | 6 ms | 5028 KB | Output is correct |

19 | Correct | 6 ms | 4984 KB | Output is correct |

20 | Correct | 6 ms | 4976 KB | Output is correct |

21 | Correct | 6 ms | 5112 KB | Output is correct |

22 | Correct | 6 ms | 4984 KB | Output is correct |

23 | Correct | 6 ms | 4984 KB | Output is correct |

24 | Correct | 6 ms | 4984 KB | Output is correct |

25 | Correct | 6 ms | 4984 KB | Output is correct |

26 | Correct | 6 ms | 4984 KB | Output is correct |

27 | Correct | 6 ms | 4984 KB | Output is correct |

28 | Correct | 6 ms | 4984 KB | Output is correct |

29 | Correct | 7 ms | 5112 KB | Output is correct |

30 | Correct | 6 ms | 5112 KB | Output is correct |

31 | Correct | 6 ms | 5112 KB | Output is correct |

32 | Correct | 6 ms | 4984 KB | Output is correct |

33 | Correct | 6 ms | 4984 KB | Output is correct |

34 | Correct | 6 ms | 4984 KB | Output is correct |

35 | Correct | 6 ms | 4984 KB | Output is correct |

36 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

2 | Correct | 6 ms | 5112 KB | Output is correct |

3 | Correct | 6 ms | 5112 KB | Output is correct |

4 | Correct | 7 ms | 4988 KB | Output is correct |

5 | Correct | 6 ms | 4984 KB | Output is correct |

6 | Correct | 6 ms | 4984 KB | Output is correct |

7 | Correct | 6 ms | 4984 KB | Output is correct |

8 | Correct | 6 ms | 4988 KB | Output is correct |

9 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

12 | Correct | 6 ms | 4984 KB | Output is correct |

13 | Correct | 6 ms | 4984 KB | Output is correct |

14 | Correct | 6 ms | 4984 KB | Output is correct |

15 | Correct | 9 ms | 5112 KB | Output is correct |

16 | Correct | 7 ms | 4984 KB | Output is correct |

17 | Correct | 8 ms | 4856 KB | Output is correct |

18 | Correct | 8 ms | 5112 KB | Output is correct |

19 | Correct | 7 ms | 5112 KB | Output is correct |

20 | Correct | 15 ms | 5880 KB | Output is correct |

21 | Correct | 16 ms | 5880 KB | Output is correct |

22 | Runtime error | 94 ms | 19352 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |

23 | Halted | 0 ms | 0 KB | - |

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

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

2 | Correct | 6 ms | 4984 KB | Output is correct |

3 | Correct | 6 ms | 5112 KB | Output is correct |

4 | Correct | 7 ms | 5112 KB | Output is correct |

5 | Runtime error | 84 ms | 29276 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |

6 | Halted | 0 ms | 0 KB | - |

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

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

2 | Correct | 6 ms | 5112 KB | Output is correct |

3 | Correct | 6 ms | 4984 KB | Output is correct |

4 | Correct | 6 ms | 4984 KB | Output is correct |

5 | Correct | 6 ms | 4984 KB | Output is correct |

6 | Correct | 6 ms | 4984 KB | Output is correct |

7 | Correct | 6 ms | 5112 KB | Output is correct |

8 | Correct | 6 ms | 4984 KB | Output is correct |

9 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

12 | Correct | 6 ms | 5112 KB | Output is correct |

13 | Correct | 6 ms | 4984 KB | Output is correct |

14 | Correct | 6 ms | 4984 KB | Output is correct |

15 | Correct | 6 ms | 4956 KB | Output is correct |

16 | Correct | 6 ms | 4984 KB | Output is correct |

17 | Correct | 6 ms | 4984 KB | Output is correct |

18 | Correct | 6 ms | 5028 KB | Output is correct |

19 | Correct | 6 ms | 4984 KB | Output is correct |

20 | Correct | 6 ms | 4976 KB | Output is correct |

21 | Correct | 6 ms | 5112 KB | Output is correct |

22 | Correct | 6 ms | 4984 KB | Output is correct |

23 | Correct | 6 ms | 4984 KB | Output is correct |

24 | Correct | 6 ms | 4984 KB | Output is correct |

25 | Correct | 6 ms | 4984 KB | Output is correct |

26 | Correct | 6 ms | 4984 KB | Output is correct |

27 | Correct | 6 ms | 4984 KB | Output is correct |

28 | Correct | 6 ms | 4984 KB | Output is correct |

29 | Correct | 7 ms | 5112 KB | Output is correct |

30 | Correct | 6 ms | 5112 KB | Output is correct |

31 | Correct | 6 ms | 5112 KB | Output is correct |

32 | Correct | 6 ms | 4984 KB | Output is correct |

33 | Correct | 6 ms | 4984 KB | Output is correct |

34 | Correct | 6 ms | 4984 KB | Output is correct |

35 | Correct | 6 ms | 4984 KB | Output is correct |

36 | Correct | 6 ms | 5112 KB | Output is correct |

37 | Correct | 6 ms | 4984 KB | Output is correct |

38 | Correct | 6 ms | 4984 KB | Output is correct |

39 | Correct | 8 ms | 4984 KB | Output is correct |

40 | Correct | 6 ms | 4984 KB | Output is correct |

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

42 | Correct | 7 ms | 5084 KB | Output is correct |

43 | Correct | 7 ms | 5104 KB | Output is correct |

44 | Correct | 7 ms | 5112 KB | Output is correct |

45 | Correct | 8 ms | 5072 KB | Output is correct |

46 | Correct | 8 ms | 5112 KB | Output is correct |

47 | Correct | 7 ms | 5112 KB | Output is correct |

48 | Correct | 7 ms | 5112 KB | Output is correct |

49 | Correct | 7 ms | 5112 KB | Output is correct |

50 | Correct | 7 ms | 5112 KB | Output is correct |

51 | Correct | 7 ms | 5112 KB | Output is correct |

52 | Correct | 7 ms | 5112 KB | Output is correct |

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

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

2 | Correct | 6 ms | 5112 KB | Output is correct |

3 | Correct | 6 ms | 4984 KB | Output is correct |

4 | Correct | 6 ms | 4984 KB | Output is correct |

5 | Correct | 6 ms | 4984 KB | Output is correct |

6 | Correct | 6 ms | 4984 KB | Output is correct |

7 | Correct | 6 ms | 5112 KB | Output is correct |

8 | Correct | 6 ms | 4984 KB | Output is correct |

9 | Correct | 6 ms | 5112 KB | Output is correct |

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

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

12 | Correct | 6 ms | 5112 KB | Output is correct |

13 | Correct | 6 ms | 4984 KB | Output is correct |

14 | Correct | 6 ms | 4984 KB | Output is correct |

15 | Correct | 6 ms | 4956 KB | Output is correct |

16 | Correct | 6 ms | 4984 KB | Output is correct |

17 | Correct | 6 ms | 4984 KB | Output is correct |

18 | Correct | 6 ms | 5028 KB | Output is correct |

19 | Correct | 6 ms | 4984 KB | Output is correct |

20 | Correct | 6 ms | 4976 KB | Output is correct |

21 | Correct | 6 ms | 5112 KB | Output is correct |

22 | Correct | 6 ms | 4984 KB | Output is correct |

23 | Correct | 6 ms | 4984 KB | Output is correct |

24 | Correct | 6 ms | 4984 KB | Output is correct |

25 | Correct | 6 ms | 4984 KB | Output is correct |

26 | Correct | 6 ms | 4984 KB | Output is correct |

27 | Correct | 6 ms | 4984 KB | Output is correct |

28 | Correct | 6 ms | 4984 KB | Output is correct |

29 | Correct | 7 ms | 5112 KB | Output is correct |

30 | Correct | 6 ms | 5112 KB | Output is correct |

31 | Correct | 6 ms | 5112 KB | Output is correct |

32 | Correct | 6 ms | 4984 KB | Output is correct |

33 | Correct | 6 ms | 4984 KB | Output is correct |

34 | Correct | 6 ms | 4984 KB | Output is correct |

35 | Correct | 6 ms | 4984 KB | Output is correct |

36 | Correct | 6 ms | 5112 KB | Output is correct |

37 | Correct | 6 ms | 5112 KB | Output is correct |

38 | Correct | 7 ms | 4988 KB | Output is correct |

39 | Correct | 6 ms | 4984 KB | Output is correct |

40 | Correct | 6 ms | 4984 KB | Output is correct |

41 | Correct | 6 ms | 4984 KB | Output is correct |

42 | Correct | 6 ms | 4988 KB | Output is correct |

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

44 | Correct | 6 ms | 5112 KB | Output is correct |

45 | Correct | 6 ms | 4988 KB | Output is correct |

46 | Correct | 6 ms | 4984 KB | Output is correct |

47 | Correct | 6 ms | 4984 KB | Output is correct |

48 | Correct | 6 ms | 4984 KB | Output is correct |

49 | Correct | 9 ms | 5112 KB | Output is correct |

50 | Correct | 7 ms | 4984 KB | Output is correct |

51 | Correct | 8 ms | 4856 KB | Output is correct |

52 | Correct | 8 ms | 5112 KB | Output is correct |

53 | Correct | 7 ms | 5112 KB | Output is correct |

54 | Correct | 15 ms | 5880 KB | Output is correct |

55 | Correct | 16 ms | 5880 KB | Output is correct |

56 | Runtime error | 94 ms | 19352 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |

57 | Halted | 0 ms | 0 KB | - |