QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#569984#8222. 投票游戏wsyear15 680ms14208kbC++231.6kb2024-09-17 13:04:442024-09-17 13:04:45

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 13:04:45]
  • 评测
  • 测评结果:15
  • 用时:680ms
  • 内存:14208kb
  • [2024-09-17 13:04:44]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 200010;
const int maxm = maxn * 4;
mt19937 rnd(1145141);

int sid, n, q, fa[maxn], rt[maxn], ls[maxm], rs[maxm], kval[maxm], tot;
ll a[maxn], b[maxn], f[maxn], bsum[maxn], g[maxn];
pll t[maxm];
vector<int> e[maxn];

void solve(int u) {
  vector<pll> vec;
  ll sum = 0;
  for (int v : e[u]) {
    solve(v), sum += b[v];
    vec.emplace_back(f[v], v);
  }
  // 按照 f[v] 排序之后第一个 a[u] + sum - sumb[i - 1] > f[i] 的位置
  // 也就是 a[u] + sum > f[i] + sumb[i - 1]
  sort(ALL(vec), greater<>());
  rep (i, 0, SZ(vec) - 1) {
    if (a[u] + sum > vec[i].fi) return f[u] = a[u] + sum, void();
    sum -= b[vec[i].se];
  }
  f[u] = a[u];
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> q;
  rep (i, 2, n) cin >> fa[i];
  rep (i, 2, n) e[fa[i]].emplace_back(i);
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) cin >> b[i], bsum[fa[i]] += b[i];
  solve(1);
  while (q--) {
    int op, x, y;
    cin >> op >> x;
    if (op == 1) {
      cin >> a[x] >> b[x];
    } else {
      cin >> y;
      solve(1);
      cout << (pll(f[x], x) > pll(f[y], y) ? 0 : 1) << '\n';
    }
  }
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 13828kb

input:

20 500
1 1 3 1 3 5 6 6 7 3 5 3 9 5 4 7 7 18 2
42129194 82765784 1447057 29726963 82321558 32094641 22474113 49277574 27527633 20746795 47630926 92888389 26787144 80703040 43876864 97991729 12117966 75633318 33577855 93462601
69163546 49621952 45236756 46447931 34085269 55246550 54414402 99593046 103...

output:

0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
1
1
0
1
1
0
0
0
0
1
1
1
1
1
1
0
1
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
0
1
0
0
1
1
1
1
0
0
1
0
0
0
1
0
1
1
1
...

result:

ok 238 numbers

Test #2:

score: 5
Accepted
time: 2ms
memory: 13820kb

input:

20 500
1 1 3 1 3 5 3 4 2 4 3 12 6 7 12 6 4 11 10
2 0 2 1 1 1 2 0 2 2 1 0 0 2 1 0 1 0 1 1
0 0 2 0 0 0 1 2 2 2 0 2 2 2 1 0 1 0 1 1
2 5 2
1 6 1 0
1 7 1 1
2 5 11
2 18 16
2 13 7
2 4 3
1 6 0 0
1 5 0 2
2 16 12
2 5 18
2 8 16
1 4 0 0
2 5 2
1 19 2 2
1 10 0 0
1 15 2 2
2 12 14
1 12 1 1
1 13 1 2
1 3 2 2
1 6 2 2
...

output:

0
1
0
1
1
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
1
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
...

result:

ok 226 numbers

Test #3:

score: 5
Accepted
time: 0ms
memory: 11792kb

input:

500 500
1 2 1 1 3 4 7 3 9 9 4 9 5 9 1 16 2 9 18 13 1 17 19 20 25 13 1 10 29 17 16 8 5 26 10 31 37 9 26 18 41 5 26 44 40 11 32 37 43 2 3 5 25 53 31 7 25 23 29 40 33 26 56 53 24 25 31 40 43 62 2 21 24 65 75 69 27 38 16 55 77 38 79 20 46 48 80 81 22 55 28 64 91 13 22 76 77 25 34 44 101 41 62 73 99 20 2...

output:

0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
1
0
1
0
0
0
1
0
1
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
1
0
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
0
1
0
0
1
1
1
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
0
1
1
1
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
...

result:

ok 247 numbers

Test #4:

score: 5
Accepted
time: 6ms
memory: 9880kb

input:

500 500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

1
1
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
1
1
0
0
0
1
1
1
1
0
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
1
0
1
1
0
0
0
1
1
1
0
0
0
1
0
1
1
1
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
1
0
...

result:

ok 255 numbers

Test #5:

score: 5
Accepted
time: 3ms
memory: 14128kb

input:

500 500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
0
0
0
1
0
1
1
1
1
0
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
0
1
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1
1
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
0
1
0
0
0
0
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
1
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
...

result:

ok 243 numbers

Test #6:

score: 5
Accepted
time: 6ms
memory: 14208kb

input:

500 500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

1
0
0
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
0
0
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
0
1
1
1
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
0
...

result:

ok 248 numbers

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 10
Accepted
time: 5ms
memory: 9956kb

input:

100 3000
1 1 2 1 3 4 1 4 7 8 1 9 5 7 2 9 7 7 1 3 20 22 16 18 23 15 24 4 14 1 21 4 21 32 14 14 33 28 13 4 20 27 41 43 18 26 4 8 24 16 30 16 13 45 20 46 6 17 4 48 24 23 54 59 61 42 62 41 26 35 10 40 9 41 35 68 67 63 48 53 10 59 81 54 15 22 86 69 49 52 55 3 27 52 48 15 54 16 87
32745005 92702519 399483...

output:

0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
0
1
0
1
1
1
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
...

result:

ok 1494 numbers

Test #8:

score: 10
Accepted
time: 5ms
memory: 13820kb

input:

100 3000
1 2 3 1 1 5 7 7 1 3 3 6 7 9 12 2 11 5 19 20 10 16 7 7 3 22 16 24 5 27 22 13 24 24 24 25 5 11 16 22 40 26 6 39 14 2 46 21 43 50 20 27 28 7 54 41 55 16 36 26 38 46 4 29 63 12 45 64 28 47 53 33 28 28 44 17 27 36 41 22 39 55 32 79 57 64 76 48 45 45 61 69 73 67 68 92 36 66 73
0 1 2 2 0 0 1 0 2 1...

output:

0
1
0
1
1
1
1
0
1
0
1
1
1
0
0
1
0
0
0
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
0
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
...

result:

ok 1495 numbers

Test #9:

score: 10
Accepted
time: 119ms
memory: 14008kb

input:

3000 3000
1 1 2 1 1 4 7 1 1 9 6 7 1 14 11 1 16 6 17 20 4 18 4 21 22 23 17 19 20 15 6 22 4 2 28 16 19 19 24 2 31 38 20 33 1 44 13 21 10 42 40 27 4 34 25 22 15 53 43 12 11 31 54 24 31 27 16 43 41 69 23 38 70 66 58 60 7 60 30 61 28 26 14 30 55 22 49 37 31 6 59 22 39 8 56 17 35 67 1 63 43 6 82 41 56 30 ...

output:

1
0
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
1
1
1
0
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
0
0
...

result:

ok 1450 numbers

Test #10:

score: 10
Accepted
time: 156ms
memory: 10332kb

input:

3000 3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

0
0
1
0
0
0
1
1
0
1
1
0
1
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
1
1
1
1
0
0
0
1
0
0
1
1
1
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
1
1
0
1
1
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
0
0
0
1
...

result:

ok 1532 numbers

Test #11:

score: 10
Accepted
time: 242ms
memory: 9860kb

input:

3000 3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
1
1
0
0
1
1
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
...

result:

ok 1481 numbers

Test #12:

score: 10
Accepted
time: 153ms
memory: 10328kb

input:

3000 3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
1
0
1
1
0
1
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
0
0
1
0
1
1
0
0
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
1
1
0
1
0
0
1
1
...

result:

ok 1541 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Test #13:

score: 10
Accepted
time: 416ms
memory: 9796kb

input:

200 200000
1 2 3 3 5 3 1 6 2 9 11 5 5 2 4 9 17 8 1 4 10 20 18 20 23 13 16 28 15 4 6 27 26 11 30 25 10 2 13 23 25 35 4 8 40 43 36 26 7 27 45 35 14 31 54 45 9 8 9 54 16 32 62 9 29 2 43 39 34 39 27 2 52 56 6 9 48 26 66 28 35 57 79 13 71 61 38 43 80 26 61 26 79 1 24 64 79 15 41 42 56 55 6 24 92 43 89 76...

output:

0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
0
...

result:

ok 100045 numbers

Test #14:

score: 10
Accepted
time: 415ms
memory: 9796kb

input:

200 200000
1 2 3 2 1 5 2 8 9 2 6 7 12 11 9 6 16 15 11 2 17 13 23 7 23 12 22 2 12 28 11 22 9 7 11 10 16 36 25 5 8 20 41 38 19 38 2 16 38 6 44 33 42 41 42 37 36 33 49 35 13 3 9 26 50 48 31 65 3 2 13 64 8 12 55 69 67 35 59 58 16 43 1 21 64 41 5 85 22 81 66 54 6 44 25 26 53 78 58 42 7 25 68 30 86 9 36 3...

output:

1
0
1
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
0
1
1
0
0
1
0
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
0
0
0
1
0
0
1
0
1
1
0
1
0
1
1
1
1
0
0
1
1
...

result:

ok 99983 numbers

Test #15:

score: 0
Time Limit Exceeded

input:

2000 200000
1 1 3 4 3 2 5 1 8 9 2 7 6 7 6 12 5 7 15 8 16 10 18 23 6 19 24 14 23 8 6 22 18 14 8 5 36 4 30 14 19 11 28 1 15 23 11 16 24 46 10 34 1 9 17 21 2 9 13 27 13 5 43 46 14 19 49 58 32 15 38 11 18 1 30 69 51 5 59 49 21 31 1 75 44 78 6 52 5 11 12 91 16 32 4 27 40 80 13 53 95 54 76 76 63 27 2 102 ...

output:

0
1
1
1
0
1
1
0
0
1
1
1
1
1
0
1
1
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
1
1
0
1
1
0
0
1
1
...

result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #18:

score: 25
Accepted
time: 584ms
memory: 9800kb

input:

200 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
1
0
1
1
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
...

result:

ok 99788 numbers

Test #19:

score: 25
Accepted
time: 570ms
memory: 10044kb

input:

200 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
0
1
1
1
1
0
1
0
0
1
1
0
0
0
1
1
1
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
...

result:

ok 99818 numbers

Test #20:

score: 0
Time Limit Exceeded

input:

2000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0
0
1
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
0
0
0
1
0
1
0
0
1
1
1
1
0
1
0
...

result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #26:

score: 20
Accepted
time: 672ms
memory: 9756kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
0
1
1
0
0
0
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
0
1
0
0
0
1
0
1
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
0
1
1
1
0
...

result:

ok 100455 numbers

Test #27:

score: 20
Accepted
time: 680ms
memory: 9752kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

0
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
0
1
1
1
1
0
0
...

result:

ok 99902 numbers

Test #28:

score: 0
Time Limit Exceeded

input:

2000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
1
1
1
...

result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%