oj.uz

Submission #986909

# Submission time Handle Problem Language Result Execution time Memory
986909 2024-05-21T14:37:16 Z PagodePaiva Arranging Shoes (IOI19_shoes) C++17
50 / 100
 190 ms 276368 KB 
#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
const int N = 400010;
queue <int> q[N];
int res[N];
int dp[N];

struct Segtree{
	int tree[4*N];
	int join(int a, int b){
		return a+b;
	}
	void build(int node, int l,int r){
		if(l == r){
			tree[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = 0;
		return;
	}
	void update(int node, int l, int r, int pos){
		if(l == r){
			tree[node] = 1;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos);
		else update(2*node+1, mid+1, r, pos);
		tree[node] = join(tree[2*node], tree[2*node+1]);
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return 0;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg;

long long count_swaps(std::vector<int> v) {
	int n = v.size();
	int num = n;
	for(int i = v.size()-1;i >= 0;i--){
		if(q[v[i]+n].empty()){
			if(v[i] > 0){
				res[i+1] = num;
				q[n-v[i]].push(num-1);
			}
			else{
				res[i+1] = num-1;
				q[n-v[i]].push(num);
			}
			num -= 2;
		}
		else{
			res[i+1] = q[v[i]+n].front();
			q[v[i]+n].pop();
		}
	}
	int resp = 0;
	for(int i = 1;i <= n;i++){
		// cout << res[i] << ' ';
		resp += seg.query(1, res[i], n, 1, n);
		seg.update(1, 1, n, res[i]);
	}
	return resp;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 270672 KB Output is correct
2 Correct 148 ms 270676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 270672 KB Output is correct
2 Correct 148 ms 270676 KB Output is correct
3 Correct 136 ms 270672 KB Output is correct
4 Correct 128 ms 270672 KB Output is correct
5 Correct 146 ms 270676 KB Output is correct
6 Correct 130 ms 270652 KB Output is correct
7 Correct 134 ms 270680 KB Output is correct
8 Correct 130 ms 270556 KB Output is correct
9 Correct 129 ms 270672 KB Output is correct
10 Correct 127 ms 270672 KB Output is correct
11 Correct 127 ms 270676 KB Output is correct
12 Correct 128 ms 270732 KB Output is correct
13 Correct 130 ms 270668 KB Output is correct
14 Correct 128 ms 270672 KB Output is correct
15 Correct 131 ms 270552 KB Output is correct
16 Correct 128 ms 270676 KB Output is correct
17 Correct 127 ms 270676 KB Output is correct
18 Correct 132 ms 270676 KB Output is correct
19 Correct 130 ms 270676 KB Output is correct
20 Correct 127 ms 270648 KB Output is correct
21 Correct 127 ms 270672 KB Output is correct
22 Correct 130 ms 270660 KB Output is correct
23 Correct 128 ms 270504 KB Output is correct
24 Correct 137 ms 270816 KB Output is correct
25 Correct 129 ms 270672 KB Output is correct
26 Correct 128 ms 270672 KB Output is correct
27 Correct 135 ms 270676 KB Output is correct
28 Correct 136 ms 270964 KB Output is correct
29 Correct 131 ms 270672 KB Output is correct
30 Correct 141 ms 270496 KB Output is correct
31 Correct 128 ms 270668 KB Output is correct
32 Correct 159 ms 270508 KB Output is correct
33 Correct 147 ms 270668 KB Output is correct
34 Correct 131 ms 270700 KB Output is correct
35 Correct 131 ms 270676 KB Output is correct
36 Correct 138 ms 270508 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 270672 KB Output is correct
2 Correct 148 ms 270676 KB Output is correct
3 Correct 125 ms 270676 KB Output is correct
4 Correct 134 ms 270856 KB Output is correct
5 Correct 146 ms 270500 KB Output is correct
6 Correct 146 ms 270536 KB Output is correct
7 Correct 129 ms 270704 KB Output is correct
8 Correct 162 ms 270672 KB Output is correct
9 Correct 143 ms 270704 KB Output is correct
10 Correct 157 ms 270676 KB Output is correct
11 Correct 128 ms 270672 KB Output is correct
12 Correct 131 ms 270672 KB Output is correct
13 Correct 132 ms 270672 KB Output is correct
14 Correct 131 ms 270908 KB Output is correct
15 Correct 129 ms 270676 KB Output is correct
16 Correct 146 ms 270508 KB Output is correct
17 Correct 132 ms 270532 KB Output is correct
18 Correct 127 ms 270788 KB Output is correct
19 Correct 129 ms 270676 KB Output is correct
20 Correct 154 ms 271256 KB Output is correct
21 Correct 133 ms 271300 KB Output is correct
22 Correct 183 ms 275952 KB Output is correct
23 Correct 172 ms 276052 KB Output is correct
24 Correct 178 ms 276148 KB Output is correct
25 Incorrect 183 ms 276368 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 270536 KB Output is correct
2 Correct 129 ms 270600 KB Output is correct
3 Correct 134 ms 270672 KB Output is correct
4 Correct 144 ms 270728 KB Output is correct
5 Incorrect 190 ms 276152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 270672 KB Output is correct
2 Correct 148 ms 270676 KB Output is correct
3 Correct 136 ms 270672 KB Output is correct
4 Correct 128 ms 270672 KB Output is correct
5 Correct 146 ms 270676 KB Output is correct
6 Correct 130 ms 270652 KB Output is correct
7 Correct 134 ms 270680 KB Output is correct
8 Correct 130 ms 270556 KB Output is correct
9 Correct 129 ms 270672 KB Output is correct
10 Correct 127 ms 270672 KB Output is correct
11 Correct 127 ms 270676 KB Output is correct
12 Correct 128 ms 270732 KB Output is correct
13 Correct 130 ms 270668 KB Output is correct
14 Correct 128 ms 270672 KB Output is correct
15 Correct 131 ms 270552 KB Output is correct
16 Correct 128 ms 270676 KB Output is correct
17 Correct 127 ms 270676 KB Output is correct
18 Correct 132 ms 270676 KB Output is correct
19 Correct 130 ms 270676 KB Output is correct
20 Correct 127 ms 270648 KB Output is correct
21 Correct 127 ms 270672 KB Output is correct
22 Correct 130 ms 270660 KB Output is correct
23 Correct 128 ms 270504 KB Output is correct
24 Correct 137 ms 270816 KB Output is correct
25 Correct 129 ms 270672 KB Output is correct
26 Correct 128 ms 270672 KB Output is correct
27 Correct 135 ms 270676 KB Output is correct
28 Correct 136 ms 270964 KB Output is correct
29 Correct 131 ms 270672 KB Output is correct
30 Correct 141 ms 270496 KB Output is correct
31 Correct 128 ms 270668 KB Output is correct
32 Correct 159 ms 270508 KB Output is correct
33 Correct 147 ms 270668 KB Output is correct
34 Correct 131 ms 270700 KB Output is correct
35 Correct 131 ms 270676 KB Output is correct
36 Correct 138 ms 270508 KB Output is correct
37 Correct 131 ms 270676 KB Output is correct
38 Correct 142 ms 270588 KB Output is correct
39 Correct 130 ms 270680 KB Output is correct
40 Correct 132 ms 270676 KB Output is correct
41 Correct 134 ms 270672 KB Output is correct
42 Correct 129 ms 270676 KB Output is correct
43 Correct 128 ms 270672 KB Output is correct
44 Correct 132 ms 270676 KB Output is correct
45 Correct 134 ms 270672 KB Output is correct
46 Correct 130 ms 270620 KB Output is correct
47 Correct 130 ms 270672 KB Output is correct
48 Correct 130 ms 270540 KB Output is correct
49 Correct 127 ms 270676 KB Output is correct
50 Correct 131 ms 270672 KB Output is correct
51 Correct 129 ms 270676 KB Output is correct
52 Correct 128 ms 270628 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 270672 KB Output is correct
2 Correct 148 ms 270676 KB Output is correct
3 Correct 136 ms 270672 KB Output is correct
4 Correct 128 ms 270672 KB Output is correct
5 Correct 146 ms 270676 KB Output is correct
6 Correct 130 ms 270652 KB Output is correct
7 Correct 134 ms 270680 KB Output is correct
8 Correct 130 ms 270556 KB Output is correct
9 Correct 129 ms 270672 KB Output is correct
10 Correct 127 ms 270672 KB Output is correct
11 Correct 127 ms 270676 KB Output is correct
12 Correct 128 ms 270732 KB Output is correct
13 Correct 130 ms 270668 KB Output is correct
14 Correct 128 ms 270672 KB Output is correct
15 Correct 131 ms 270552 KB Output is correct
16 Correct 128 ms 270676 KB Output is correct
17 Correct 127 ms 270676 KB Output is correct
18 Correct 132 ms 270676 KB Output is correct
19 Correct 130 ms 270676 KB Output is correct
20 Correct 127 ms 270648 KB Output is correct
21 Correct 127 ms 270672 KB Output is correct
22 Correct 130 ms 270660 KB Output is correct
23 Correct 128 ms 270504 KB Output is correct
24 Correct 137 ms 270816 KB Output is correct
25 Correct 129 ms 270672 KB Output is correct
26 Correct 128 ms 270672 KB Output is correct
27 Correct 135 ms 270676 KB Output is correct
28 Correct 136 ms 270964 KB Output is correct
29 Correct 131 ms 270672 KB Output is correct
30 Correct 141 ms 270496 KB Output is correct
31 Correct 128 ms 270668 KB Output is correct
32 Correct 159 ms 270508 KB Output is correct
33 Correct 147 ms 270668 KB Output is correct
34 Correct 131 ms 270700 KB Output is correct
35 Correct 131 ms 270676 KB Output is correct
36 Correct 138 ms 270508 KB Output is correct
37 Correct 125 ms 270676 KB Output is correct
38 Correct 134 ms 270856 KB Output is correct
39 Correct 146 ms 270500 KB Output is correct
40 Correct 146 ms 270536 KB Output is correct
41 Correct 129 ms 270704 KB Output is correct
42 Correct 162 ms 270672 KB Output is correct
43 Correct 143 ms 270704 KB Output is correct
44 Correct 157 ms 270676 KB Output is correct
45 Correct 128 ms 270672 KB Output is correct
46 Correct 131 ms 270672 KB Output is correct
47 Correct 132 ms 270672 KB Output is correct
48 Correct 131 ms 270908 KB Output is correct
49 Correct 129 ms 270676 KB Output is correct
50 Correct 146 ms 270508 KB Output is correct
51 Correct 132 ms 270532 KB Output is correct
52 Correct 127 ms 270788 KB Output is correct
53 Correct 129 ms 270676 KB Output is correct
54 Correct 154 ms 271256 KB Output is correct
55 Correct 133 ms 271300 KB Output is correct
56 Correct 183 ms 275952 KB Output is correct
57 Correct 172 ms 276052 KB Output is correct
58 Correct 178 ms 276148 KB Output is correct
59 Incorrect 183 ms 276368 KB Output isn't correct
60 Halted 0 ms 0 KB -