﻿

# BattleDev November 26, 2020: Question 4 (wrong way)

Nov 26th, 2020 (edited)
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python3
2. # -*- coding: utf-8 -*-
3.
4. """
5. BattleDev November 26, 2020
6. Question 4
7. Wrong way.
8. See better way in https://pastebin.com/riarp6VG
9. """
10.
11. import sys
12.
13.
14. def main() -> None:
15.     n, m = map(int, input().split())
16.
17.     xs = tuple(map(int, input().split()))
18.
19.     # print(xs, file=sys.stderr)
20.
21.     assert len(xs) == n
22.
23.     lrs = []
24.     for line in sys.stdin:
25.         l, r = map(int, line.split())
26.         lrs.append((l, r))
27.
28.     assert len(lrs) == m
29.
30.     # print(lrs, file=sys.stderr)
31.
32.     dlrs = dict()
33.     for l, r in lrs:
34.         if l not in dlrs:
35.             dlrs[l] = []
36.         dlrs[l].append(r)
37.
38.     for rs in dlrs.values():
39.         rs.sort()
40.
41.     # print(dlrs, file=sys.stderr)
42.
43.     d = {i: 0 for i in range(256)}
44.     for l, rs in dlrs.items():
45.         x = 0
46.         i = l
47.         for r in rs:
48.             # while (i <= r) and (x < 255):  # probably the good way, but WTF somewhere
49.             while i <= r:  # correct but not enough efficient
50.                 x ^= xs[i]
51.                 i += 1
52.
53.             d[x] += 1
54.
55.     print(' '.join(str(nb) for nb in d.values()))
56.
57.
58. if __name__ == '__main__':
59.     main()
60.
RAW Paste Data