提出 #73138178

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e5 + 10;

int T, n, m, a[MAXN], b[MAXN], pos[MAXN], c[MAXN];

inline void add(int k) { for (int i = k; i <= n; i += i & -i) c[i]++; }
inline int ask(int k) { int res = 0; for (int i = k; i; i &= i - 1) res += c[i]; return res; }

deque<int> p[MAXN]; int pt[MAXN];

vector<tuple<int, int, int>> g[MAXN]; int qcnt; ll ans[MAXN];

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
		for (int i = 1; i <= n; i++) p[i].clear(), pt[i] = pos[i] = 0;
		for (int i = 1; i <= n; i++) p[b[i]].emplace_back(i);
		for (int i = 1; i <= n; i++) a[i] = p[a[i]][pt[a[i]]++], pos[a[i]] = i;
//		for (int i = 1; i <= n; i++) printf("%d ", a[i]); puts("");
		qcnt = 0;
		for (int i = 1; i <= n; i++) g[i].clear();
		for (int i = 1; i <= n; i++) {
			if (p[i].size() < 2) continue;
			for (int j = 1; j < p[i].size(); j++) {
				int x = p[i][j - 1], y = p[i][j];
				int u = pos[x], v = pos[y]; qcnt++;
//				printf("[%d,%d]:%d %d\n", x, y, u, v);
				g[u + 1].emplace_back(x, -1, qcnt);
				g[u + 1].emplace_back(y - 1, 1, qcnt);
				g[v].emplace_back(x, 1, qcnt);
				g[v].emplace_back(y - 1, -1, qcnt);
			}
		}
		for (int i = 1; i <= qcnt; i++) ans[i] = 0;
		ll sum = 0, res = 1e18;
		for (int i = 1; i <= n; i++) c[i] = 0;
		for (int i = n; i; i--) {
			sum += ask(a[i]), add(a[i]);
			for (auto _ : g[i]) ans[get<2>(_)] += get<1>(_) * ask(get<0>(_));
		}
		for (int i = 1; i <= qcnt; i++) res = min(res, ans[i] << 1 | 1);
//		for (int i = 1; i <= qcnt; i++) printf("%lld ", ans[i]); puts("");
		ll k = (sum + m - 1) / m; sum = m * k - sum;
		if (sum & 1) {
			if (m & 1) {
				if (res <= sum) printf("%lld\n", k);
				else printf("%lld\n", k + 1);
			} else {
				if (res < 1e18) printf("%lld\n", (max<ll>(0, res - sum) + m - 1) / m + k);
				else puts("-1");
			}
		} else printf("%lld\n", k);
	}
}

提出情報

コンパイルエラー

./Main.cpp: In function 'int main()':
./Main.cpp:31:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                         for (int j = 1; j < p[i].size(); j++) {
      |                                         ~~^~~~~~~~~~~~~

ジャッジ結果