結果
問題 | No.2382 Amidakuji M |
ユーザー | flygon |
提出日時 | 2023-07-14 22:51:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 2,786 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 86,836 KB |
実行使用メモリ | 112,496 KB |
最終ジャッジ日時 | 2023-10-14 13:10:37 |
合計ジャッジ時間 | 4,662 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,496 KB |
testcase_01 | AC | 76 ms
71,560 KB |
testcase_02 | AC | 78 ms
71,700 KB |
testcase_03 | AC | 181 ms
91,896 KB |
testcase_04 | AC | 197 ms
105,428 KB |
testcase_05 | AC | 119 ms
80,156 KB |
testcase_06 | AC | 168 ms
93,904 KB |
testcase_07 | AC | 142 ms
86,492 KB |
testcase_08 | AC | 107 ms
78,756 KB |
testcase_09 | AC | 186 ms
98,868 KB |
testcase_10 | AC | 221 ms
108,964 KB |
testcase_11 | AC | 149 ms
89,000 KB |
testcase_12 | AC | 200 ms
100,844 KB |
testcase_13 | AC | 79 ms
71,436 KB |
testcase_14 | AC | 77 ms
71,456 KB |
testcase_15 | AC | 78 ms
71,332 KB |
testcase_16 | AC | 78 ms
71,704 KB |
testcase_17 | AC | 76 ms
71,728 KB |
testcase_18 | AC | 78 ms
71,720 KB |
testcase_19 | AC | 246 ms
112,164 KB |
testcase_20 | AC | 249 ms
112,496 KB |
testcase_21 | AC | 246 ms
112,312 KB |
ソースコード
import sys sys.setrecursionlimit(5*10**5) input = sys.stdin.readline from collections import defaultdict, deque, Counter from heapq import heappop, heappush from bisect import bisect_left, bisect_right from math import gcd def add(x, y): return x + y def e(a): if a == min: return 10**18 if a == max: return -10**18 if a == add: return 0 class SegTree: def __init__(self, segf, init_val): n = len(init_val) self.segf = segf self.e = e(segf) self.seg_len = 1 << n.bit_length() self.seg = [self.e] * 2*self.seg_len for i in range(n): self.seg[i + self.seg_len] = init_val[i] for i in range(self.seg_len)[::-1]: self.seg[i] = segf(self.seg[i << 1], self.seg[i << 1 | 1]) def point_add(self, pos, x): pos += self.seg_len self.seg[pos] += x while True: pos >>= 1 if not pos: break self.seg[pos] = self.segf( self.seg[pos << 1], self.seg[pos << 1 | 1]) def point_update(self, pos, x): pos += self.seg_len self.seg[pos] = x while True: pos >>= 1 if not pos: break self.seg[pos] = self.segf( self.seg[pos << 1], self.seg[pos << 1 | 1]) def get_range(self, l, r): l += self.seg_len r += self.seg_len res = self.e while l < r: if l & 1: res = self.segf(res, self.seg[l]) l += 1 if r & 1: r -= 1 res = self.segf(res, self.seg[r]) l >>= 1 r >>= 1 return res # ------ range_add & get_point ------- def range_add(self, l, r, x): l += self.seg_len r += self.seg_len self.seg[l] += x self.seg[r] += x while l < r: if l & 1: self.seg[l] = self.segf(x, self.seg[l]) l += 1 if r & 1: r -= 1 self.seg[r] = self.segf(x, self.seg[r]) l >>= 1 r >>= 1 def get_point(self, pos): pos += self.seg_len res = self.seg[pos] while True: pos >>= 1 if not pos: break res = self.segf(res, self.seg[pos]) return res n,m = map(int,input().split()) p = list(map(int,input().split())) st = SegTree(add,[0]*(n+10)) ans = 0 for i in range(n): ans += st.get_range(p[i],n+5) st.point_add(p[i],1) if ans == 0: print(0) elif m % 2 == 0 and ans % 2 == 1: print(-1) else: mn = m *( (ans+m-1)//m) if (mn - ans) % 2 == 0: print(mn) else: print(mn + m)