Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
int r = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
r += x;
cout << r / m << ' ';
r %= m;
}
cout << '\n';
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 1000 + 7;
int pr[N];
bool ok[N];
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
string s, t;
static char buf[N];
scanf("%s", buf);
s = buf;
scanf("%s", buf);
t = buf;
pr[0] = 0;
forn(i, n - m + 1){
bool fl = true;
forn(j, m)
if (s[i + j] != t[j])
fl = false;
ok[i] = fl;
pr[i + 1] = pr[i] + ok[i];
}
for (int i = max(0, n - m + 1); i < n; ++i){
pr[i + 1] = pr[i];
}
forn(i, q){
int l, r;
scanf("%d%d", &l, &r);
--l, r -= m - 1;
printf("%d\n", r >= l ? pr[r] - pr[l] : 0);
}
return 0;
}
1016C - Vasya And The Mushrooms
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = 300 * 1000 + 9;
int n;
int a[2][N];
long long sum123[2][N];
long long sum321[2][N];
long long sum111[2][N];
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < 2; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &a[i][j]);
for(int i = 0; i < 2; ++i)
for(int j = n - 1; j >= 0; --j){
sum123[i][j] = sum123[i][j + 1] + (j + 1) * 1LL * a[i][j];
sum321[i][j] = sum321[i][j + 1] + (n - j) * 1LL * a[i][j];
sum111[i][j] = sum111[i][j + 1] + a[i][j];
}
/* for(int i = 0; i < 2; ++i)
for(int j = n - 1; j >= 0; --j){
cout << i << ' ' << j << " : ";
cout << sum123[i][j] << " " << sum321[i][j] << " " << sum111[i][j] << endl;
} */
long long res = 0, sum = 0;
for(int i = 0, j = 0; j < n; ++j, i ^= 1){
long long nres = sum;
nres += sum123[i][j] + j * 1LL * sum111[i][j];
nres += sum321[i ^ 1][j] + (j + n) * 1LL * sum111[i ^ 1][j];
res = max(res, nres);
sum += a[i][j] * 1ll * (j + j + 1);
sum += a[i ^ 1][j] * 1ll * (j + j + 2);
}
for(int j = 0; j < n; ++j) res -= a[0][j] + a[1][j];
printf("%I64d\n", res);
return 0;
}
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
#include "testlib.h"
using namespace std;
const int N = 109;
int n, m;
int a[N], b[N];
int res[N][N];
int main() {
int cur = 0;
cin >> n >> m;
for(int i = 0; i < n; ++i)
cin >> a[i], cur ^= a[i];
for(int i = 0; i < m; ++i)
cin >> b[i], cur ^= b[i];
if(cur != 0){
puts("NO");
return 0;
}
puts("YES");
for(int i = 1; i < m; ++i)
cur ^= b[i];
cur ^= a[0];
cout << cur << ' ';
for(int i = 1; i < m; ++i)
cout << b[i] << ' ';
cout << endl;
for(int i = 1; i < n; ++i){
cout << a[i] << ' ';
for(int j = 1; j < m; ++j)
cout << 0 << ' ';
cout << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const double EPS = 1e-9;
const int N = 200 * 1000 + 555;
li sy, a, b;
int n, q;
pt s[N], p[N];
inline bool read() {
if(!(cin >> sy >> a >> b))
return false;
assert(cin >> n);
fore(i, 0, n)
assert(scanf("%lld%lld", &s[i].x, &s[i].y) == 2);
assert(cin >> q);
fore(i, 0, q)
assert(scanf("%lld%lld", &p[i].x, &p[i].y) == 2);
return true;
}
int getGE(ld x) {
for(int pos = max(int(lower_bound(s, s + n, pt(li(x), -1)) - s) - 2, 0); pos < n; pos++)
if(x <= s[pos].x)
return pos;
return n;
}
li ps[N];
li getSum(int l, int r) {
li ans = r > 0 ? ps[r - 1] : 0;
ans -= l > 0 ? ps[l - 1] : 0;
return ans;
}
inline void solve() {
fore(i, 0, n) {
ps[i] = s[i].y - s[i].x;
if(i > 0)
ps[i] += ps[i - 1];
}
fore(i, 0, q) {
ld lx = p[i].x + (a - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
ld rx = p[i].x + (b - p[i].x) * (ld(p[i].y) / (p[i].y - sy));
int posL = getGE(lx);
int posR = getGE(rx) - 1;
ld sum = getSum(posL, posR);
if(posL > 0)
sum += max(ld(0.0), s[posL - 1].y - max((ld)s[posL - 1].x, lx));
if(posR >= 0)
sum += max(ld(0.0), min((ld)s[posR].y, rx) - s[posR].x);
sum *= ld(p[i].y - sy) / p[i].y;
printf("%.15f\n", double(sum));
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
The first solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const long long INF64 = (long long)(1e18);
const int N = 1000 * 1000 + 13;
int n, m;
vector<pair<int, int>> g[N];
long long d[N];
int siz[N];
int tin[N], tout[N], T;
int pr[N];
void calc(int v, int p){
pr[v] = p;
tin[v] = T++;
siz[v] = 1;
for (auto it : g[v]){
int u = it.first;
int w = it.second;
if (u == p) continue;
d[u] = d[v] + w;
calc(u, v);
siz[v] += siz[u];
}
tout[v] = T++;
}
inline int isp(int v, int u){
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
long long dif;
long long mn;
void dfs(int v, int p){
dif = min(dif, max(0ll, -(mn - d[v])));
if (p != -1 && pr[p] != -1)
dif = min(dif, max(0ll, -(d[pr[p]] - d[v])));
for (auto it : g[v]){
int u = it.first;
int w = it.second;
if (u == p) continue;
if (!isp(u, n - 1)){
dif = min(dif, max(0ll, -(mn + w - d[v])));
mn = max(mn, w + d[v]);
if (p != -1)
dif = min(dif, max(0ll, -(w - d[v] + d[p])));
}
}
for (auto it : g[v]){
int u = it.first;
if (u == p) continue;
if (isp(u, n - 1))
dfs(u, v);
}
}
int main() {
scanf("%d%d", &n, &m);
forn(i, n - 1){
int v, u, w;
scanf("%d%d%d", &v, &u, &w);
--v, --u;
g[v].push_back(make_pair(u, w));
g[u].push_back(make_pair(v, w));
}
T = 0;
calc(0, -1);
long long cur = d[n - 1];
dif = INF64;
mn = -INF64;
forn(i, n)
if (!isp(i, n - 1) && siz[i] > 1)
dif = 0;
if (dif > 0)
dfs(0, -1);
forn(i, m){
int x;
scanf("%d", &x);
printf("%lld\n", min(cur, cur - dif + x));
}
return 0;
}
The second solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > g;
vector<long long> d;
vector<long long> d1;
vector<long long> dn;
int n, q;
bool read()
{
scanf("%d %d", &n, &q);
g.resize(n);
d.resize(n);
for(int i = 0; i < n - 1; i++)
{
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
--x;
--y;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
return true;
}
void dfs(int x, int p = -1, long long dist = 0)
{
d[x] = dist;
for (auto e : g[x])
if (p != e.first)
dfs(e.first, x, e.second + dist);
}
void solve()
{
dfs(0);
d1 = d;
dfs(n - 1);
dn = d;
set<pair<long long, int> > dists_n;
vector<pair<long long, int> > order;
for(int i = 0; i < n; i++)
order.push_back(make_pair(d1[i] - dn[i], i));
sort(order.begin(), order.end());
for(int i = 0; i < n; i++)
dists_n.insert(make_pair(dn[i], i));
vector<int> pos(n);
for(int i = 0; i < n; i++)
pos[order[i].second] = i;
long long T = (long long)(1e18);
for(int i = 0; i < n; i++)
{
int v = order[i].second;
dists_n.erase(make_pair(dn[v], v));
for (auto e : g[v])
if (pos[e.first] > pos[v])
dists_n.erase(make_pair(dn[e.first], e.first));
if (!dists_n.empty())
T = min(T, d1[n - 1] - d1[v] - dists_n.rbegin()->first);
for (auto e : g[v])
if (pos[e.first] > pos[v])
dists_n.insert(make_pair(dn[e.first], e.first));
}
for(int i = 0; i < q; i++)
{
int x;
scanf("%d", &x);
printf("%lld\n", d1[n - 1] - max(0ll, T - x));
}
}
int main()
{
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
if (read())
{
solve();
}
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
const int N = 200 * 1000 + 555;
int n; li x, y;
li a[N];
inline bool read() {
if(!(cin >> n >> x >> y))
return false;
fore(i, 0, n)
assert(scanf("%lld", &a[i]) == 1);
return true;
}
li gcd(li a, li b) {
while(a > 0) {
b %= a;
swap(a, b);
}
return b;
}
vector<pt> factorize(li v) {
vector<pt> f;
for(li x = 2; x <= 1'000'000 && x * x <= v; x++) {
int cnt = 0;
while(v % x == 0)
v /= x, cnt++;
if(cnt > 0)
f.emplace_back(x, cnt);
}
if(v > 1) {
for(li s = max(1ll, (li)sqrtl(v) - 2); s * s <= v; s++)
if(s * s == v) {
f.emplace_back(s, 2);
v = 1;
break;
}
if(v > 1) {
vector<li> cnd(a, a + n);
cnd.push_back(x);
cnd.push_back(y);
for(li c : cnd) {
li g = gcd(v, c);
if(g != 1 && g != v) {
li a = g, b = v / g;
if(a > b)
swap(a, b);
f.emplace_back(a, 1);
f.emplace_back(b, 1);
v = 1;
break;
}
}
if(v > 1)
f.emplace_back(v, 1), v = 1;
}
}
return f;
}
int d[(1 << 18) + 3];
inline void solve() {
if(y % x != 0) {
puts("0");
return;
}
vector<pt> fy = factorize(y);
vector<pt> fx;
li cx = x;
for(auto p : fy) {
int cnt = 0;
while(cx % p.x == 0)
cx /= p.x, cnt++;
fx.emplace_back(p.x, cnt);
}
vector<li> ps;
vector<pt> bb;
fore(i, 0, sz(fy)) {
if(fx[i].y < fy[i].y) {
ps.push_back(fy[i].x);
bb.emplace_back(fx[i].y, fy[i].y);
}
}
fore(i, 0, n) {
if(a[i] % x != 0)
continue;
int mask = 0;
li ca = a[i];
fore(j, 0, sz(ps)) {
int cnt = 0;
while(ca % ps[j] == 0)
ca /= ps[j], cnt++;
assert(cnt >= bb[j].x);
mask |= (cnt > bb[j].x) << j;
}
d[mask]++;
}
for(int i = 0; i < sz(ps); i++) {
fore(mask, 0, 1 << sz(ps))
if((mask >> i) & 1)
d[mask] += d[mask ^ (1 << i)];
}
li ans = 0;
fore(i, 0, n) {
if(y % a[i] != 0)
continue;
int mask = 0;
li ca = a[i];
fore(j, 0, sz(ps)) {
int cnt = 0;
while(ca % ps[j] == 0)
ca /= ps[j], cnt++;
assert(cnt <= bb[j].y);
mask |= (cnt < bb[j].y) << j;
}
ans += d[mask ^ ((1 << sz(ps)) - 1)];
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}