oj.uz

Submission #808834

# Submission time Handle Problem Language Result Execution time Memory
808834 2023-08-05T11:35:52 Z OrazB Arranging Shoes (IOI19_shoes) C++14
100 / 100
 290 ms 275864 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 2e5+5;
deque<int> lft[N], rgt[N];

ll count_swaps(vector<int> S){
	int n = S.size();
	S.insert(S.begin(), -1);
	for (int i = 1; i <= n; i++){
		if (S[i] > 0) rgt[S[i]].pb(i);
		else lft[-S[i]].pb(i);	
	}
	ll ans = 0;
	ordered_set s;
	for (int i = 1; i <= n; i++){
		if (s.find(i) != s.end()) continue;
		int j = 0;
		while(s.size() and (*s.begin()) <= i) s.erase(s.begin());
		if (S[i] > 0) j = lft[S[i]].front();
		else j = rgt[-S[i]].front();
		lft[abs(S[i])].pop_front();
		rgt[abs(S[i])].pop_front();
		ans += (j-i-s.order_of_key(j)-(S[i] < 0));
		s.insert(j);
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 269516 KB Output is correct
2 Correct 141 ms 269552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 269516 KB Output is correct
2 Correct 141 ms 269552 KB Output is correct
3 Correct 124 ms 269516 KB Output is correct
4 Correct 132 ms 269548 KB Output is correct
5 Correct 123 ms 269564 KB Output is correct
6 Correct 129 ms 269516 KB Output is correct
7 Correct 127 ms 269512 KB Output is correct
8 Correct 125 ms 269484 KB Output is correct
9 Correct 124 ms 269564 KB Output is correct
10 Correct 126 ms 269568 KB Output is correct
11 Correct 129 ms 269564 KB Output is correct
12 Correct 126 ms 269468 KB Output is correct
13 Correct 130 ms 269448 KB Output is correct
14 Correct 135 ms 269480 KB Output is correct
15 Correct 128 ms 269552 KB Output is correct
16 Correct 130 ms 269564 KB Output is correct
17 Correct 144 ms 269556 KB Output is correct
18 Correct 130 ms 269496 KB Output is correct
19 Correct 125 ms 269516 KB Output is correct
20 Correct 125 ms 269480 KB Output is correct
21 Correct 126 ms 269516 KB Output is correct
22 Correct 138 ms 269548 KB Output is correct
23 Correct 146 ms 269556 KB Output is correct
24 Correct 124 ms 269536 KB Output is correct
25 Correct 127 ms 269476 KB Output is correct
26 Correct 130 ms 269516 KB Output is correct
27 Correct 130 ms 269500 KB Output is correct
28 Correct 131 ms 269460 KB Output is correct
29 Correct 129 ms 269576 KB Output is correct
30 Correct 129 ms 269504 KB Output is correct
31 Correct 135 ms 269492 KB Output is correct
32 Correct 134 ms 269532 KB Output is correct
33 Correct 129 ms 269500 KB Output is correct
34 Correct 127 ms 269544 KB Output is correct
35 Correct 129 ms 269504 KB Output is correct
36 Correct 128 ms 269452 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 269516 KB Output is correct
2 Correct 141 ms 269552 KB Output is correct
3 Correct 132 ms 269552 KB Output is correct
4 Correct 128 ms 269520 KB Output is correct
5 Correct 129 ms 269560 KB Output is correct
6 Correct 126 ms 269480 KB Output is correct
7 Correct 128 ms 269524 KB Output is correct
8 Correct 128 ms 269556 KB Output is correct
9 Correct 126 ms 269516 KB Output is correct
10 Correct 125 ms 269516 KB Output is correct
11 Correct 131 ms 269716 KB Output is correct
12 Correct 149 ms 269532 KB Output is correct
13 Correct 158 ms 269508 KB Output is correct
14 Correct 128 ms 269552 KB Output is correct
15 Correct 132 ms 269560 KB Output is correct
16 Correct 130 ms 269560 KB Output is correct
17 Correct 128 ms 269468 KB Output is correct
18 Correct 132 ms 269488 KB Output is correct
19 Correct 138 ms 269468 KB Output is correct
20 Correct 144 ms 269768 KB Output is correct
21 Correct 156 ms 269792 KB Output is correct
22 Correct 169 ms 271968 KB Output is correct
23 Correct 164 ms 271976 KB Output is correct
24 Correct 165 ms 271932 KB Output is correct
25 Correct 187 ms 275820 KB Output is correct
26 Correct 181 ms 271904 KB Output is correct
27 Correct 168 ms 271956 KB Output is correct
28 Correct 188 ms 275756 KB Output is correct
29 Correct 191 ms 275780 KB Output is correct
30 Correct 189 ms 275816 KB Output is correct
31 Correct 184 ms 271932 KB Output is correct
32 Correct 190 ms 275752 KB Output is correct
33 Correct 195 ms 275800 KB Output is correct
34 Correct 187 ms 275800 KB Output is correct
35 Correct 159 ms 269516 KB Output is correct
36 Correct 137 ms 269580 KB Output is correct
37 Correct 190 ms 275848 KB Output is correct
38 Correct 190 ms 275772 KB Output is correct
39 Correct 185 ms 275844 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 269496 KB Output is correct
2 Correct 123 ms 269516 KB Output is correct
3 Correct 122 ms 269544 KB Output is correct
4 Correct 139 ms 269516 KB Output is correct
5 Correct 280 ms 275728 KB Output is correct
6 Correct 234 ms 275724 KB Output is correct
7 Correct 270 ms 275728 KB Output is correct
8 Correct 204 ms 275820 KB Output is correct
9 Correct 253 ms 275828 KB Output is correct
10 Correct 290 ms 275812 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 269516 KB Output is correct
2 Correct 141 ms 269552 KB Output is correct
3 Correct 124 ms 269516 KB Output is correct
4 Correct 132 ms 269548 KB Output is correct
5 Correct 123 ms 269564 KB Output is correct
6 Correct 129 ms 269516 KB Output is correct
7 Correct 127 ms 269512 KB Output is correct
8 Correct 125 ms 269484 KB Output is correct
9 Correct 124 ms 269564 KB Output is correct
10 Correct 126 ms 269568 KB Output is correct
11 Correct 129 ms 269564 KB Output is correct
12 Correct 126 ms 269468 KB Output is correct
13 Correct 130 ms 269448 KB Output is correct
14 Correct 135 ms 269480 KB Output is correct
15 Correct 128 ms 269552 KB Output is correct
16 Correct 130 ms 269564 KB Output is correct
17 Correct 144 ms 269556 KB Output is correct
18 Correct 130 ms 269496 KB Output is correct
19 Correct 125 ms 269516 KB Output is correct
20 Correct 125 ms 269480 KB Output is correct
21 Correct 126 ms 269516 KB Output is correct
22 Correct 138 ms 269548 KB Output is correct
23 Correct 146 ms 269556 KB Output is correct
24 Correct 124 ms 269536 KB Output is correct
25 Correct 127 ms 269476 KB Output is correct
26 Correct 130 ms 269516 KB Output is correct
27 Correct 130 ms 269500 KB Output is correct
28 Correct 131 ms 269460 KB Output is correct
29 Correct 129 ms 269576 KB Output is correct
30 Correct 129 ms 269504 KB Output is correct
31 Correct 135 ms 269492 KB Output is correct
32 Correct 134 ms 269532 KB Output is correct
33 Correct 129 ms 269500 KB Output is correct
34 Correct 127 ms 269544 KB Output is correct
35 Correct 129 ms 269504 KB Output is correct
36 Correct 128 ms 269452 KB Output is correct
37 Correct 136 ms 269568 KB Output is correct
38 Correct 132 ms 269532 KB Output is correct
39 Correct 119 ms 269476 KB Output is correct
40 Correct 133 ms 269532 KB Output is correct
41 Correct 135 ms 269492 KB Output is correct
42 Correct 120 ms 269556 KB Output is correct
43 Correct 130 ms 269520 KB Output is correct
44 Correct 123 ms 269588 KB Output is correct
45 Correct 137 ms 269496 KB Output is correct
46 Correct 134 ms 269600 KB Output is correct
47 Correct 126 ms 269596 KB Output is correct
48 Correct 125 ms 269624 KB Output is correct
49 Correct 130 ms 269556 KB Output is correct
50 Correct 153 ms 269592 KB Output is correct
51 Correct 143 ms 269632 KB Output is correct
52 Correct 138 ms 269536 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 269516 KB Output is correct
2 Correct 141 ms 269552 KB Output is correct
3 Correct 124 ms 269516 KB Output is correct
4 Correct 132 ms 269548 KB Output is correct
5 Correct 123 ms 269564 KB Output is correct
6 Correct 129 ms 269516 KB Output is correct
7 Correct 127 ms 269512 KB Output is correct
8 Correct 125 ms 269484 KB Output is correct
9 Correct 124 ms 269564 KB Output is correct
10 Correct 126 ms 269568 KB Output is correct
11 Correct 129 ms 269564 KB Output is correct
12 Correct 126 ms 269468 KB Output is correct
13 Correct 130 ms 269448 KB Output is correct
14 Correct 135 ms 269480 KB Output is correct
15 Correct 128 ms 269552 KB Output is correct
16 Correct 130 ms 269564 KB Output is correct
17 Correct 144 ms 269556 KB Output is correct
18 Correct 130 ms 269496 KB Output is correct
19 Correct 125 ms 269516 KB Output is correct
20 Correct 125 ms 269480 KB Output is correct
21 Correct 126 ms 269516 KB Output is correct
22 Correct 138 ms 269548 KB Output is correct
23 Correct 146 ms 269556 KB Output is correct
24 Correct 124 ms 269536 KB Output is correct
25 Correct 127 ms 269476 KB Output is correct
26 Correct 130 ms 269516 KB Output is correct
27 Correct 130 ms 269500 KB Output is correct
28 Correct 131 ms 269460 KB Output is correct
29 Correct 129 ms 269576 KB Output is correct
30 Correct 129 ms 269504 KB Output is correct
31 Correct 135 ms 269492 KB Output is correct
32 Correct 134 ms 269532 KB Output is correct
33 Correct 129 ms 269500 KB Output is correct
34 Correct 127 ms 269544 KB Output is correct
35 Correct 129 ms 269504 KB Output is correct
36 Correct 128 ms 269452 KB Output is correct
37 Correct 132 ms 269552 KB Output is correct
38 Correct 128 ms 269520 KB Output is correct
39 Correct 129 ms 269560 KB Output is correct
40 Correct 126 ms 269480 KB Output is correct
41 Correct 128 ms 269524 KB Output is correct
42 Correct 128 ms 269556 KB Output is correct
43 Correct 126 ms 269516 KB Output is correct
44 Correct 125 ms 269516 KB Output is correct
45 Correct 131 ms 269716 KB Output is correct
46 Correct 149 ms 269532 KB Output is correct
47 Correct 158 ms 269508 KB Output is correct
48 Correct 128 ms 269552 KB Output is correct
49 Correct 132 ms 269560 KB Output is correct
50 Correct 130 ms 269560 KB Output is correct
51 Correct 128 ms 269468 KB Output is correct
52 Correct 132 ms 269488 KB Output is correct
53 Correct 138 ms 269468 KB Output is correct
54 Correct 144 ms 269768 KB Output is correct
55 Correct 156 ms 269792 KB Output is correct
56 Correct 169 ms 271968 KB Output is correct
57 Correct 164 ms 271976 KB Output is correct
58 Correct 165 ms 271932 KB Output is correct
59 Correct 187 ms 275820 KB Output is correct
60 Correct 181 ms 271904 KB Output is correct
61 Correct 168 ms 271956 KB Output is correct
62 Correct 188 ms 275756 KB Output is correct
63 Correct 191 ms 275780 KB Output is correct
64 Correct 189 ms 275816 KB Output is correct
65 Correct 184 ms 271932 KB Output is correct
66 Correct 190 ms 275752 KB Output is correct
67 Correct 195 ms 275800 KB Output is correct
68 Correct 187 ms 275800 KB Output is correct
69 Correct 159 ms 269516 KB Output is correct
70 Correct 137 ms 269580 KB Output is correct
71 Correct 190 ms 275848 KB Output is correct
72 Correct 190 ms 275772 KB Output is correct
73 Correct 185 ms 275844 KB Output is correct
74 Correct 142 ms 269496 KB Output is correct
75 Correct 123 ms 269516 KB Output is correct
76 Correct 122 ms 269544 KB Output is correct
77 Correct 139 ms 269516 KB Output is correct
78 Correct 280 ms 275728 KB Output is correct
79 Correct 234 ms 275724 KB Output is correct
80 Correct 270 ms 275728 KB Output is correct
81 Correct 204 ms 275820 KB Output is correct
82 Correct 253 ms 275828 KB Output is correct
83 Correct 290 ms 275812 KB Output is correct
84 Correct 136 ms 269568 KB Output is correct
85 Correct 132 ms 269532 KB Output is correct
86 Correct 119 ms 269476 KB Output is correct
87 Correct 133 ms 269532 KB Output is correct
88 Correct 135 ms 269492 KB Output is correct
89 Correct 120 ms 269556 KB Output is correct
90 Correct 130 ms 269520 KB Output is correct
91 Correct 123 ms 269588 KB Output is correct
92 Correct 137 ms 269496 KB Output is correct
93 Correct 134 ms 269600 KB Output is correct
94 Correct 126 ms 269596 KB Output is correct
95 Correct 125 ms 269624 KB Output is correct
96 Correct 130 ms 269556 KB Output is correct
97 Correct 153 ms 269592 KB Output is correct
98 Correct 143 ms 269632 KB Output is correct
99 Correct 138 ms 269536 KB Output is correct
100 Correct 135 ms 269512 KB Output is correct
101 Correct 155 ms 269928 KB Output is correct
102 Correct 144 ms 269748 KB Output is correct
103 Correct 234 ms 273428 KB Output is correct
104 Correct 179 ms 271900 KB Output is correct
105 Correct 219 ms 271832 KB Output is correct
106 Correct 247 ms 275776 KB Output is correct
107 Correct 171 ms 271896 KB Output is correct
108 Correct 166 ms 271940 KB Output is correct
109 Correct 193 ms 275864 KB Output is correct
110 Correct 191 ms 275836 KB Output is correct
111 Correct 280 ms 275788 KB Output is correct
112 Correct 219 ms 274756 KB Output is correct
113 Correct 220 ms 275732 KB Output is correct
114 Correct 261 ms 275840 KB Output is correct
115 Correct 264 ms 275788 KB Output is correct