oj.uz

답안 #143479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143479 2019-08-14T08:51:10 Z dolphingarlic Arranging Shoes (IOI19_shoes) C++14
10 / 100
 359 ms 276152 KB 
#include "shoes.h"
#include <queue>
// #include <iostream>

int n;
long long bit[100001];
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();

				// std::cout << i + 1 << ' ' << r_indx << " l before r\n";

				ans += r_indx - i - 2 - query(i + 1, r_indx);
				update(r_indx);

				// std::cout << ans << '\n';
			}
		} else {
			if (right[s[i]].front() == i + 1) {
				int l_indx = left[s[i]].front();
				right[s[i]].pop();
				left[s[i]].pop();

				// std::cout << i + 1 << ' ' << l_indx << " r before l\n";

				ans += l_indx - i - 1 - query(i + 1, l_indx);

				// std::cout << ans << '\n';
			}
		}
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 134904 KB Output is correct
2 Correct 137 ms 134904 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 134904 KB Output is correct
2 Correct 137 ms 134904 KB Output is correct
3 Correct 140 ms 135012 KB Output is correct
4 Correct 138 ms 134904 KB Output is correct
5 Correct 151 ms 134904 KB Output is correct
6 Correct 138 ms 134904 KB Output is correct
7 Correct 138 ms 135008 KB Output is correct
8 Correct 139 ms 134904 KB Output is correct
9 Correct 141 ms 134952 KB Output is correct
10 Correct 139 ms 135004 KB Output is correct
11 Correct 138 ms 134872 KB Output is correct
12 Correct 138 ms 134952 KB Output is correct
13 Correct 139 ms 134876 KB Output is correct
14 Incorrect 138 ms 134908 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 134904 KB Output is correct
2 Correct 137 ms 134904 KB Output is correct
3 Correct 142 ms 134928 KB Output is correct
4 Correct 140 ms 134968 KB Output is correct
5 Correct 138 ms 134904 KB Output is correct
6 Correct 139 ms 134992 KB Output is correct
7 Correct 140 ms 135032 KB Output is correct
8 Correct 168 ms 134904 KB Output is correct
9 Incorrect 139 ms 134904 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 134904 KB Output is correct
2 Correct 138 ms 134940 KB Output is correct
3 Correct 140 ms 134984 KB Output is correct
4 Correct 139 ms 134904 KB Output is correct
5 Runtime error 359 ms 276152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 134904 KB Output is correct
2 Correct 137 ms 134904 KB Output is correct
3 Correct 140 ms 135012 KB Output is correct
4 Correct 138 ms 134904 KB Output is correct
5 Correct 151 ms 134904 KB Output is correct
6 Correct 138 ms 134904 KB Output is correct
7 Correct 138 ms 135008 KB Output is correct
8 Correct 139 ms 134904 KB Output is correct
9 Correct 141 ms 134952 KB Output is correct
10 Correct 139 ms 135004 KB Output is correct
11 Correct 138 ms 134872 KB Output is correct
12 Correct 138 ms 134952 KB Output is correct
13 Correct 139 ms 134876 KB Output is correct
14 Incorrect 138 ms 134908 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 134904 KB Output is correct
2 Correct 137 ms 134904 KB Output is correct
3 Correct 140 ms 135012 KB Output is correct
4 Correct 138 ms 134904 KB Output is correct
5 Correct 151 ms 134904 KB Output is correct
6 Correct 138 ms 134904 KB Output is correct
7 Correct 138 ms 135008 KB Output is correct
8 Correct 139 ms 134904 KB Output is correct
9 Correct 141 ms 134952 KB Output is correct
10 Correct 139 ms 135004 KB Output is correct
11 Correct 138 ms 134872 KB Output is correct
12 Correct 138 ms 134952 KB Output is correct
13 Correct 139 ms 134876 KB Output is correct
14 Incorrect 138 ms 134908 KB Output isn't correct
15 Halted 0 ms 0 KB -