Tutorial is loading...
Code
#include <random>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define pii pair<int, int>
#define pb emplace_back
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &c : a) cin >> c;
int mx = 0;
for (int i = 0; i < n - 1; i++) mx = max(mx, a[i]);
cout << mx + a[n - 1] << "\n";
}
return 0;
}
Tutorial is loading...
Code
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long n, a, b;
cin >> n >> a >> b;
if (b <= a) {
cout << n * a << endl;
} else {
long long k = min(b — a + 1, n);
cout << (b — k + 1) * n + k * (k — 1) / 2 << endl;
}
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
int n;
ll k;
cin >> n >> k;
ll max_s = 0;
for (int i = 0; i < n; i++) max_s += abs(n — 1 — i — i);
if (k % 2 != 0 || k > max_s) {
cout << "No\n";
} else {
cout << "Yes\n";
vector<int> p(n);
k /= 2;
iota(p.begin(), p.end(), 0);
for (int i = 0; k > 0; i++) {
if (k >= n — 1 — 2 * i) {
swap(p[i], p[n — 1 — i]);
k -= n — 1 — 2 * i;
} else {
swap(p[i], p[i + k]);
k = 0;
}
}
for (int i = 0; i < n; i++) {
cout << p[i] + 1 << " ";
}
cout << "\n";
}
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) {
cout << "0\n";
return;
}
int mx = *max_element(a.begin() + 1, a.end());
int mxc = max(a[0] + c, mx);
int winner = mxc == a[0] + c ? 0 : find(a.begin() + 1, a.end(), mx) - a.begin();
ll sum = c;
for (int i = 0; i < n; sum += a[i], ++i) {
int answer;
if (i == winner) {
answer = 0;
} else if (sum + a[i] >= mx) {
answer = i;
} else {
answer = i + 1;
}
cout << answer << " \n"[i == n - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int main () {
ios_base::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
string s, t;
cin >> n >> s >> t;
auto get_range = [&] (int i) {
if (s[i] == '1') return make_pair(i, i);
int l = -1, r = -1;
if (i > 0 && t[i-1] == '1') l = i-1;
else if (i > 1 && t[i-1] == '0' && s[i-2] == '0') l = i-2;
if (i+1 < n && t[i+1] == '1') r = i+1;
else if (i+2 < n && t[i+1] == '0' && s[i+2] == '0') r = i+2;
if (l == -1) r = -1;
if (r == -1) l = -1;
return make_pair(l, r);
};
vector<int> pref(n+1);
for (int i = 0; i < n; i++) pref[i+1] = pref[i] + (get_range(i).first != -1);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int ans = 0;
if (r-l <= 5) {
for (int i = l-1; i < r; i++) {
auto [ll, rr] = get_range(i);
if (ll >= l-1 && rr < r) ans++;
}
}
else {
ans = pref[r] - pref[l-1];
for (int j: {l-1, l, r-2, r-1}) {
auto [ll, rr] = get_range(j);
if (ll != -1 && (ll < l-1 || rr >= r)) ans--;
}
}
cout << ans << '\n';
}
}
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
using namespace std;
using ll = long long;
const int MAXA = 1e6;
int n, k;
vector<int> a;
vector<int> primes_x[MAXA + 1];
unordered_map<int, int> last_ind_p;
vector<bool> is_prime(MAXA + 1, true);
vector<int> primes;
void read() {
cin >> n >> k;
a.assign(n, 0);
for (int& elem : a) {
cin >> elem;
}
}
vector<int> p, sz, p_rs;
int col(int A) {
return (A == p[A] ? A : p[A] = col(p[A]));
}
void unique(int A, int B) {
A = col(A); B = col(B);
if (A == B) return;
if (sz[A] < sz[B]) {
swap(A, B);
}
p[B] = A;
sz[A] += sz[B];
}
void solve() {
last_ind_p.clear();
vector<int> aa;
for (int i = 1; i < n; i++) {
aa.push_back(a[i]);
}
for (int i = 0; i < n; i++) {
aa.push_back(a[i]);
}
a = aa;
int n2 = n;
n = a.size();
p.assign(n, -1);
p_rs.assign(n, -1);
sz.assign(n, -1);
for (int i = 0; i < n; i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n2; i++) {
p_rs[i] = i + 1;
p_rs[2 * n2 - 2 - i] = i + 1;
}
vector<int> a2 = a;
sort(a2.begin(), a2.end());
a2.resize(unique(a2.begin(), a2.end()) - a2.begin());
unordered_set<int> to_clean;
for (int elem : a2) {
int cur_elem = elem;
for (ll p : primes) {
if (p * p > elem) break;
if (elem % p == 0) {
primes_x[cur_elem].push_back(p);
if (primes_x[cur_elem].size() == 1) {
to_clean.insert(cur_elem);
}
}
while (elem % p == 0) {
elem /= p;
}
}
if (elem > 1) {
primes_x[cur_elem].push_back(elem);
if (primes_x[cur_elem].size() == 1) {
to_clean.insert(cur_elem);
}
}
}
for (int i = 0; i < n; i++) {
for (int cur_p : primes_x[a[i]]) {
if (last_ind_p.count(cur_p) && i - last_ind_p[cur_p] <= k) {
unique(last_ind_p[cur_p], i);
}
last_ind_p[cur_p] = i;
}
}
for (int i : to_clean)
primes_x[i].clear();
}
void write() {
ll ans = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i) {
if (a[i] > 1) {
ans += 1;
}
else {
ans += p_rs[i];
}
}
}
cout << ans << endl;
}
int main() {
for (ll i = 2; i <= MAXA; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (ll j = i * i; j <= MAXA; j += i) {
is_prime[j] = false;
}
}
}
ios_base::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
read();
solve();
write();
}
}