题解 - Codeforces Round #791 Div. 2 (A-D)

比赛链接

A - AvtoBus

Spring has come, and the management of the AvtoBus bus fleet has given the order to replace winter tires with summer tires on all buses

You own a small bus service business and you have just received an order to replace \(n\) tires. You know that the bus fleet owns two types of buses: with two axles (these buses have \(4\) wheels) and with three axles (these buses have \(6\) wheels)

You don't know how many buses of which type the AvtoBus bus fleet owns, so you wonder how many buses the fleet might have. You have to determine the minimum and the maximum number of buses that can be in the fleet if you know that the total number of wheels for all buses is \(n\)

Input

The first line contains an integer \(t\) (\(1 \le t \le 1\,000\)) — the number of test cases. The following lines contain description of test cases

The only line of each test case contains one integer \(n\) (\(1 \le n \le 10^{18}\)) — the total number of wheels for all buses

Output

For each test case print the answer in a single line using the following format

Print two integers \(x\) and \(y\) (\(1 \le x \le y\)) — the minimum and the maximum possible number of buses that can be in the bus fleet

If there is no suitable number of buses for the given \(n\), print the number \(-1\) as the answer

Example

input

4
4
7
24
998244353998244352

output

1 1
-1
4 6
166374058999707392 249561088499561088

Note

In the first test case the total number of wheels is \(4\). It means that there is the only one bus with two axles in the bus fleet

In the second test case it's easy to show that there is no suitable number of buses with \(7\) wheels in total

In the third test case the total number of wheels is \(24\). The following options are possible:

• Four buses with three axles
• Three buses with two axles and two buses with three axles
• Six buses with two axles

So the minimum number of buses is \(4\) and the maximum number of buses is \(6\)

代码参考

Show code

CodeForces_1679Aview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) {
    i64 n;
    cin >> n;
    if (n < 4 || n % 2) {
      cout << "-1\n";
      continue;
    }
    i64 m = 1, M;
    M = (n % 4 == 0) ? n / 4 : (n - 6) / 4 + 1;
    if (n > 6) {
      if (n % 6 == 0) m = n / 6;
      else if ((n - 4) % 6 == 0) m = (n - 4) / 6 + 1;
      else m = (n - 8) / 6 + 2;
    }
    cout << m << " " << M << '\n';
  }
  return 0;
}

B - Stone Age Problem

Once upon a time Mike and Mike decided to come up with an outstanding problem for some stage of ROI (rare olympiad in informatics). One of them came up with a problem prototype but another stole the idea and proposed that problem for another stage of the same olympiad. Since then the first Mike has been waiting for an opportunity to propose the original idea for some other contest... Mike waited until this moment!

You are given an array \(a\) of \(n\) integers. You are also given \(q\) queries of two types:

• Replace \(i\)-th element in the array with integer \(x\)
• Replace each element in the array with integer \(x\)

After performing each query you have to calculate the sum of all elements in the array

Input

The first line contains two integers \(n\) and \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) — the number of elements in the array and the number of queries, respectively

The second line contains \(n\) integers \(a_1, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — elements of the array \(a\)

Each of the following \(q\) lines contains a description of the corresponding query. Description begins with integer \(t\) (\(t \in \{1, 2\}\)) which denotes a type of the query:

• If \(t = 1\), then two integers \(i\) and \(x\) are following (\(1 \le i \le n\), \(1 \le x \le 10^9\)) — position of replaced element and it's new value
• If \(t = 2\), then integer \(x\) is following (\(1 \le x \le 10^9\)) — new value of each element in the array

Output

Print \(q\) integers, each on a separate line. In the \(i\)-th line print the sum of all elements in the array after performing the first \(i\) queries

Example

input

5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1

output

19
50
51
42
5

Note

Consider array from the example and the result of performing each query:

1. Initial array is \([1, 2, 3, 4, 5]\)
2. After performing the first query, array equals to \([5, 2, 3, 4, 5]\). The sum of all elements is \(19\)
3. After performing the second query, array equals to \([10, 10, 10, 10, 10]\). The sum of all elements is \(50\)
4. After performing the third query, array equals to \([10, 10, 10, 10, 11\)]. The sum of all elements is \(51\)
5. After performing the fourth query, array equals to \([10, 10, 10, 1, 11]\). The sum of all elements is \(42\)
6. After performing the fifth query, array equals to \([1, 1, 1, 1, 1]\). The sum of all elements is \(5\)

解题思路

\(O(n)\) 做法属实是典中典了，懒得想也可以直接套线段树，略

代码参考

Show code

CodeForces_1679Bview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
struct Query {
  int l, r;
} q[M];
map<int, int> mp;
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  i64 ans = 0;
  int global_a = 0;
  _for(i, 1, n, x) {
    cin >> x;
    mp[i] = x;
    ans += x;
  }
  _for(i, 1, m, t, x, y) {
    cin >> t >> x;
    if (t == 2) {
      global_a = x;
      ans = 1ll * n * x;
      mp.clear();
    } else {
      cin >> y;
      if (mp[x]) {
        ans += y - mp[x];
      } else {
        ans += y - global_a;
      }
      mp[x] = y;
    }
    cout << ans << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

C - Rooks Defenders

You have a square chessboard of size \(n \times n\). Rows are numbered from top to bottom with numbers from \(1\) to \(n\), and columns — from left to right with numbers from \(1\) to \(n\). So, each cell is denoted with pair of integers \((x, y)\) (\(1 \le x, y \le n\)), where \(x\) is a row number and \(y\) is a column number

You have to perform \(q\) queries of three types:

• Put a new rook in cell \((x, y)\)
• Remove a rook from cell \((x, y)\). It's guaranteed that the rook was put in this cell before
• Check if each cell of subrectangle \((x_1, y_1) - (x_2, y_2)\) of the board is attacked by at least one rook

Subrectangle is a set of cells \((x, y)\) such that for each cell two conditions are satisfied: \(x_1 \le x \le x_2\) and \(y_1 \le y \le y_2\)

Recall that cell \((a, b)\) is attacked by a rook placed in cell \((c, d)\) if either \(a = c\) or \(b = d\). In particular, the cell containing a rook is attacked by this rook

Input

The first line contains two integers \(n\) and \(q\) (\(1 \le n \le 10^5\), \(1 \le q \le 2 \cdot 10^5\)) — the size of the chessboard and the number of queries, respectively

Each of the following \(q\) lines contains description of a query. Description begins with integer \(t\) (\(t \in \{1, 2, 3\}\)) which denotes type of a query:

• If \(t = 1\), two integers \(x\) and \(y\) follows (\(1 \le x, y \le n\)) — coordinated of the cell where the new rook should be put in. It's guaranteed that there is no rook in the cell \((x, y)\) at the moment of the given query
• If \(t = 2\), two integers \(x\) and \(y\) follows (\(1 \le x, y \le n\)) — coordinates of the cell to remove a rook from. It's guaranteed that there is a rook in the cell \((x, y)\) at the moment of the given query
• If \(t = 3\), four integers \(x_1, y_1, x_2\) and \(y_2\) follows (\(1 \le x_1 \le x_2 \le n\), \(1 \le y_1 \le y_2 \le n\)) — subrectangle to check if each cell of it is attacked by at least one rook

It's guaranteed that among \(q\) queries there is at least one query of the third type

Output

Print the answer for each query of the third type in a separate line. Print "Yes" (without quotes) if each cell of the subrectangle is attacked by at least one rook

Otherwise print "No" (without quotes)

Example

input

8 10
1 2 4
3 6 2 7 2
1 3 2
3 6 2 7 2
1 4 3
3 2 6 4 8
2 4 3
3 2 6 4 8
1 4 8
3 2 6 4 8

output

No
Yes
Yes
No
Yes

Note

Consider example. After the first two queries the board will look like the following picture (the letter \(R\) denotes cells in which rooks are located, the subrectangle of the query of the third type is highlighted in green):

Chessboard after performing the third and the fourth queries:

Chessboard after performing the fifth and the sixth queries:

Chessboard after performing the seventh and the eighth queries:

Chessboard after performing the last two queries:

解题思路

显然两个树状数组维护一下哪些点有 Rooks 就行

代码参考

Show code

CodeForces_1679Cview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET;
template <typename Tp>
class BIT {
public:
  Tp tree[N];
  constexpr size_t lowbit(ptrdiff_t x) const { return x & (-x); }

public:
  BIT() {}
  void modify(size_t pos, Tp val = 1) {
    for (size_t i = pos; i < N; i += lowbit(i)) tree[i] += val;
  }
  Tp query(size_t pos) const {
    Tp ret = 0;
    for (size_t i = pos; i; i = (ptrdiff_t)i - lowbit(i)) ret += tree[i];
    return ret;
  }
};
BIT<int> btrow, btcol;
int cntr[N], cntc[N];
auto solve() -> void {
  int n, m;
  cin >> n >> m;
  _for(i, 1, m, t, x1, y1, x2, y2) {
    cin >> t >> x1 >> y1;
    if (t == 1) {
      if (!cntr[x1]) btrow.modify(x1, 1);
      ++cntr[x1];
      if (!cntc[y1]) btcol.modify(y1, 1);
      ++cntc[y1];
    } else if (t == 2) {
      --cntr[x1];
      if (!cntr[x1]) btrow.modify(x1, -1);
      --cntc[y1];
      if (!cntc[y1]) btcol.modify(y1, -1);
    } else if (t == 3) {
      cin >> x2 >> y2;
      if (x1 > x2) swap(x1, x2);
      if (y1 > y2) swap(y1, y2);
      cout << (btrow.query(x2) - btrow.query(x1 - 1) == x2 - x1 + 1 ||
                   btcol.query(y2) - btcol.query(y1 - 1) == y2 - y1 + 1 ?
                 "Yes" :
                 "No")
           << '\n';
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}

D - Toss a Coin to Your Graph..

One day Masha was walking in the park and found a graph under a tree... Surprised? Did you think that this problem would have some logical and reasoned story? No way! So, the problem..

Masha has an oriented graph which \(i\)-th vertex contains some positive integer \(a_i\). Initially Masha can put a coin at some vertex. In one operation she can move a coin placed in some vertex \(u\) to any other vertex \(v\) such that there is an oriented edge \(u \to v\) in the graph. Each time when the coin is placed in some vertex \(i\), Masha write down an integer \(a_i\) in her notebook (in particular, when Masha initially puts a coin at some vertex, she writes an integer written at this vertex in her notebook). Masha wants to make exactly \(k - 1\) operations in such way that the maximum number written in her notebook is as small as possible

Input

The first line contains three integers \(n\), \(m\) and \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le m \le 2 \cdot 10^5\), \(1 \le k \le 10^{18}\)) — the number of vertices and edges in the graph, and the number of operation that Masha should make

The second line contains \(n\) integers \(a_i\) (\(1 \le a_i \le 10^9\)) — the numbers written in graph vertices

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u \ne v \le n\)) — it means that there is an edge \(u \to v\) in the graph

It's guaranteed that graph doesn't contain loops and multi-edges

Output

Print one integer — the minimum value of the maximum number that Masha wrote in her notebook during optimal coin movements

If Masha won't be able to perform \(k - 1\) operations, print \(-1\)

Examples

input

6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

output

4

input

6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

output

10

input

2 1 5
1 1
1 2

output

-1

input

1 0 1
1000000000

output

1000000000

Note

Graph described in the first and the second examples is illustrated below

In the first example Masha can initially put a coin at vertex \(1\). After that she can perform three operations: \(1 \to 3\), \(3 \to 4\) and \(4 \to 5\). Integers \(1, 2, 3\) and \(4\) will be written in the notepad

In the second example Masha can initially put a coin at vertex \(2\). After that she can perform \(99\) operations: \(2 \to 5\), \(5 \to 6\), \(6 \to 2\), \(2 \to 5\), and so on. Integers \(10, 4, 5, 10, 4, 5, \ldots, 10, 4, 5, 10\) will be written in the notepad

In the third example Masha won't be able to perform \(4\) operations

解题思路

面向验题人编程

二分 + 找 \(k\) 长路 + 判环

代码参考

Show code

CodeForces_1679Dview raw

/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _rfor(i, r, l, vals...)                                      \
  for (make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vals; \
       i >= i##end;                                                  \
       --i)
#define _set_nul_n(a, n) memset(a, 0, sizeof(*(a)) * (n))
const uint32_t OFFSET = 5;
const uint32_t N = 2e5 + OFFSET, M = 2e5 + OFFSET;
struct Edge {
  int to, next;
  Edge(int _to = 0, int _next = 0): to(_to), next(_next) {}
} e[M];
int head[N], cnt_edge;
void addEdge(int x, int y) {
  e[++cnt_edge] = Edge(y, head[x]);
  head[x] = cnt_edge;
}
#define _for_graph(head, e, i, now) \
  for (int i = head[now], to = e[i].to; i; to = e[i = e[i].next].to)
int n, m;
i64 k;
int a[N];
bool vis[N];
int dep[N];
int ord[N], cnt_ord;
void typo(int now, int max_a) {
  vis[now] = 1;
  _for_graph(head, e, i, now) {
    if (a[to] > max_a) continue;
    if (!vis[to]) typo(to, max_a);
  }
  ord[++cnt_ord] = now;
}
bool judge(int max_a) {
  _set_nul_n(vis, n + 1);
  _set_nul_n(ord, n + 1);
  cnt_ord = 0;
  _for(i, 1, n)
    if (a[i] <= max_a && !vis[i]) typo(i, max_a);
  _set_nul_n(vis, n + 1);
  _set_nul_n(dep, n + 1);
  _rfor(i, cnt_ord, 1) {
    _for_graph(head, e, j, ord[i]) {
      if (a[to] > max_a) continue;
      if (vis[to]) return true;
      dep[to] = max(dep[to], dep[ord[i]] + 1);
    }
    vis[ord[i]] = true;
  }
  int ans = 0;
  _for(i, 1, n) ans = max(ans, dep[i]);
  return ans + 1 >= k;
}
auto solve() -> void {
  cin >> n >> m >> k;
  int l = INT_MAX, r = 0, mid = 0, ans = 0;
  _for(i, 1, n) {
    cin >> a[i];
    r = max(r, a[i]);
    l = min(l, a[i]);
  }
  if (!k) {
    cout << l;
    return;
  }
  _for(i, 1, m, x, y) {
    cin >> x >> y;
    addEdge(x, y);
  }
  while (l <= r) {
    mid = l + (r - l) / 2;
    if (judge(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << (ans ? ans : -1);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}