Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
for (int i = 0, x; i < n; ++i) {
cin >> x;
ans |= x;
}
cout << ans << endl;
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i + 1 < n; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
if (i + 2 < n) {
a[i + 1] = max(a[i], a[i + 2]);
} else {
a[i + 1] = a[i];
}
ans++;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << " \n"[i == n - 1];
}
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (a[n - 2] > a[n - 1]) {
cout << -1 << endl;
} else {
if (a[n - 1] < 0) {
if (is_sorted(a.begin(), a.end())) {
cout << 0 << endl;
} else {
cout << -1 << endl;
}
} else {
cout << n - 2 << endl;
for (int i = 1; i <= n - 2; ++i) {
cout << i << ' ' << n - 1 << ' ' << n << endl;
}
}
}
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, p;
cin >> n >> p;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
set <int> useful;
for (int i = 0; i < n; ++i) {
int x = a[i];
bool flag = false;
while (x > 0) {
if (useful.count(x)) {
flag = true;
}
if (x & 1) {
x >>= 1;
} else if (x & 3) {
break;
} else {
x >>= 2;
}
}
if (!flag)
useful.insert(a[i]);
}
vector <int> cnt(30, 0), dp(p);
for (int x : useful) {
cnt[__lg(x)]++;
}
int ans = 0;
for (int i = 0; i < p; ++i) {
if (i < 30) {
dp[i] = cnt[i];
}
if (i >= 1) {
dp[i] += dp[i - 1];
if (dp[i] >= mod) {
dp[i] -= mod;
}
}
if (i >= 2) {
dp[i] += dp[i - 2];
if (dp[i] >= mod) {
dp[i] -= mod;
}
}
ans += dp[i];
if (ans >= mod) {
ans -= mod;
}
}
cout << ans << endl;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
struct edge {
int type, u, v;
};
vector <int> adj[N];
int col[N], topo[N];
void dfs(int v) {
for (int u : adj[v]) if (col[u] == -1) {
col[u] = col[v] ^ 1;
dfs(u);
}
}
bool BipartiteColoring(int n) {
for (int i = 1; i <= n; ++i)
col[i] = -1;
for (int i = 1; i <= n; ++i) if (col[i] == -1) {
col[i] = 0;
dfs(i);
}
for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
if (col[i] == col[j]) {
return false;
}
}
return true;
}
bool TopologicalSort(int n) {
vector <int> in(n + 1, 0);
for (int i = 1; i <= n; ++i) for (int j : adj[i]) {
in[j]++;
}
queue <int> q;
for (int i = 1; i <= n; ++i) if (in[i] == 0) {
q.push(i);
}
int ord = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
topo[v] = ord++;
for (int u : adj[v]) {
in[u]--;
if (in[u] == 0) {
q.push(u);
}
}
}
return ord == n;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <edge> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i].type >> a[i].u >> a[i].v;
adj[a[i].u].push_back(a[i].v);
adj[a[i].v].push_back(a[i].u);
}
if (!BipartiteColoring(n)) {
cout << "NO" << endl;
return 0;
}
// col = 0 -> orient left, col = 1 -> orient right
for (int i = 1; i <= n; ++i) {
adj[i].clear();
}
for (edge e : a) {
if (col[e.u] == 1)
swap(e.u, e.v);
if (e.type == 1) {
adj[e.u].push_back(e.v);
} else {
adj[e.v].push_back(e.u);
}
}
if (!TopologicalSort(n)) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
for (int i = 1; i <= n; ++i) {
cout << (col[i] == 0 ? "L " : "R ") << topo[i] << endl;
}
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
const long long INF = 1ll << 62;
vector <int> useful_pair[N];
vector <pair <int, int>> queries[N];
long long bit[N];
void modify(int p, long long v) {
for (int i = p; i > 0; i -= i & (-i)) {
bit[i] = min(bit[i], v);
}
}
long long query(int p) {
long long ans = INF;
for (int i = p; i < N; i += i & (-i)) {
ans = min(ans, bit[i]);
}
return ans;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector <int> x(n), w(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> w[i];
}
for (int i = 0, l, r; i < q; ++i) {
cin >> l >> r, --l;
queries[r].emplace_back(l, i);
}
stack <int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && w[stk.top()] > w[i]) {
stk.pop();
}
if (!stk.empty()) {
int x = stk.top();
useful_pair[i].push_back(x);
}
stk.push(i);
}
while (!stk.empty()) {
stk.pop();
}
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && w[stk.top()] > w[i]) {
stk.pop();
}
if (!stk.empty()) {
int x = stk.top();
useful_pair[x].push_back(i);
}
stk.push(i);
}
fill(bit, bit + N, INF);
vector <long long> ans(q);
for (int r = 1; r <= n; ++r) {
for (int l : useful_pair[r - 1]) {
long long val = 1ll * (x[r - 1] - x[l]) * (w[l] + w[r - 1]);
modify(l + 1, val);
}
for (auto [l, id] : queries[r]) {
ans[id] = query(l + 1);
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << endl;
}
}