Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include<bits/stdc++.h>
using namespace std;
long long n, k;
int main(){
int tc;
cin >> tc;
for(int i = 0; i < tc; ++i){
cin >> n >> k;
long long res = 0;
while(n > 0){
if(n % k == 0){
n /= k;
++res;
}
else{
long long rem = n % k;
res += rem;
n -= rem;
}
}
cout << res << endl;
}
return 0;
}
Idea: awoo
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 long long INF = 1ll << 32;
int main(){
int l;
cin >> l;
stack<long long> cur;
cur.push(1);
long long res = 0;
forn(_, l){
string t;
cin >> t;
if (t == "for"){
int x;
cin >> x;
cur.push(min(INF, cur.top() * x));
}
else if (t == "end"){
cur.pop();
}
else{
res += cur.top();
}
}
if (res >= INF)
cout << "OVERFLOW!!!" << endl;
else
cout << res << endl;
}
Idea: adedalic
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())
int n, k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
inline void solve() {
pair<int, int> ans = {int(1e9) + 7, -1};
fore(i, 0, n - k) {
int dist = a[i + k] - a[i];
ans = min(ans, make_pair(dist, a[i] + dist / 2));
}
cout << ans.second << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include<bits/stdc++.h>
using namespace std;
const int N = 300009;
int n, k;
int a[N];
int main(){
cin >> n >> k;
for(int i = 0; i < n; ++i)
cin >> a[i];
long long sum = 0;
vector <long long> v;
for(int i = n - 1; i >= 0; --i){
sum += a[i];
if(i > 0) v.push_back(sum);
}
long long res = sum;
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for(int i = 0; i < k - 1; ++i)
res += v[i];
cout << res << endl;
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution 1 (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 500 * 1000 + 13;
const int LOGN = 18;
int n, m;
pair<int, int> a[N], q[N];
int nxt[N];
int up[LOGN][N];
int main(){
scanf("%d%d", &n, &m);
forn(i, n)
scanf("%d%d", &a[i].x, &a[i].y);
forn(i, m)
scanf("%d%d", &q[i].x, &q[i].y);
sort(a, a + n);
int lst = 0;
pair<int, int> mx(0, -1);
forn(i, N){
while (lst < n && a[lst].x == i){
mx = max(mx, make_pair(a[lst].y, lst));
++lst;
}
nxt[i] = (mx.x <= i ? -1 : mx.y);
}
forn(i, n)
up[0][i] = nxt[a[i].y];
for (int j = 1; j < LOGN; ++j) forn(i, n){
if (up[j - 1][i] == -1)
up[j][i] = -1;
else
up[j][i] = up[j - 1][up[j - 1][i]];
}
forn(i, m){
int x = nxt[q[i].x];
if (x == -1){
puts("-1");
continue;
}
int res = 1;
for (int j = LOGN - 1; j >= 0; --j){
int y = up[j][x];
if (y == -1)
continue;
if (a[y].y < q[i].y){
res += (1 << j);
x = y;
}
}
if (a[x].y >= q[i].y)
printf("%d\n", res);
else if (up[0][x] == -1)
puts("-1");
else
printf("%d\n", res + 1);
}
}
Solution 2 (PikMike)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 500 * 1000 + 13;
int n, m;
pair<int, int> a[N], q[N];
int nxt[N];
int ans[N];
pair<int, int> p[N];
pair<int, int> get(int x, int r){
if (x == -1)
return make_pair(-1, -1);
if (a[x].y >= r)
return make_pair(x, 0);
auto res = get(p[x].x, r);
if (res.x == -1)
p[x] = make_pair(-1, -1);
else
p[x] = make_pair(res.x, p[x].y + res.y);
return p[x];
}
int main(){
scanf("%d%d", &n, &m);
forn(i, n)
scanf("%d%d", &a[i].x, &a[i].y);
forn(i, m)
scanf("%d%d", &q[i].x, &q[i].y);
sort(a, a + n);
int lst = 0;
pair<int, int> mx(0, -1);
forn(i, N){
while (lst < n && a[lst].x == i){
mx = max(mx, make_pair(a[lst].y, lst));
++lst;
}
nxt[i] = (mx.x <= i ? -1 : mx.y);
}
vector<int> perm(m);
iota(perm.begin(), perm.end(), 0);
sort(perm.begin(), perm.end(), [](int a, int b){
return q[a].y < q[b].y;
});
forn(i, n)
p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1);
for (auto i : perm){
int x = nxt[q[i].x];
auto res = get(x, q[i].y).y;
ans[i] = (res == -1 ? -1 : res + 1);
}
forn(i, m)
printf("%d\n", ans[i]);
}
1175F - The Number of Subpermutations
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> pt;
const int N = int(3e5) + 99;
const pt zero = make_pair(0, 0);
int n;
int a[N];
pt hsh[N], sumHsh[N];
pt prefsum[N];
void upd(pt &a, pt b){
a.first ^= b.first;
a.second ^= b.second;
}
pt f(int l, int r){
pt res = prefsum[r];
if(l > 0) upd(res, prefsum[l - 1]);
return res;
}
int calc(int pos){
int r = pos, len = 0, res = 0;
while(r < n - 1 && a[r + 1] != 0){
len = max(len, a[r + 1] + 1);
++r;
if(r - len + 1 >= 0 && f(r - len + 1, r) == sumHsh[len - 1])
++res;
}
return res;
}
int main() {
long long x = 0;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
--a[i];
x ^= a[i];
}
mt19937 rnd(time(NULL));
for(int i = 0; i < N; ++i){
hsh[i].first = rnd() ^ x;
hsh[i].second = rnd() ^ x;
sumHsh[i] = hsh[i];
if(i > 0) upd(sumHsh[i], sumHsh[i - 1]);
}
int res = 0;
for(int tc = 0; tc < 2; ++tc){
for(int i = 0; i < n; ++i){
prefsum[i] = hsh[a[i]];
if(i > 0) upd(prefsum[i], prefsum[i - 1]);
}
for(int i = 0; i < n; ++i)
if(a[i] == 0)
res += calc(i) + (tc == 0);
reverse(a, a + n);
}
cout << res << endl;
return 0;
}
1175G - Yet Another Partiton Problem
Idea: adedalic
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(1e9);
pt operator -(const pt &a, const pt &b) {
return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
return a.x * b.x + a.y * b.y;
}
li operator %(const pt &a, const pt &b) {
return a.x * b.y - a.y * b.x;
}
pt rotate(const pt &p) {
return {-p.y, p.x};
}
struct LinearHull {
deque<pt> pts, vecs;
void addRight(const pt &l) {
while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) {
vecs.pop_back();
pts.pop_back();
}
if(!pts.empty())
vecs.push_back(rotate(l - pts.back()));
pts.push_back(l);
}
void addLeft(const pt &l) {
while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) {
vecs.pop_front();
pts.pop_front();
}
if(!pts.empty())
vecs.push_front(rotate(pts.front() - l));
pts.push_front(l);
}
li getMin(const pt &x) {
auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) {
return a % b > 0;
});
return x * pts[it - vecs.begin()];
}
};
typedef unique_ptr<LinearHull> pHull;
void mergeHulls(pHull &a, pHull &b) {
if(sz(b->pts) >= sz(a->pts)) {
for(auto &p : a->pts)
b->addRight(p);
} else {
for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++)
a->addLeft(*it);
swap(a, b);
}
}
const int M = 1000 * 1000 + 555;
int szn = 0;
struct node {
pt line;
node *l, *r;
node() : line(), l(nullptr), r(nullptr) {}
node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {}
} nodes[M];
typedef node* tree;
tree getNode(const pt &line, tree l, tree r) {
assert(szn < M);
nodes[szn] = node(line, l, r);
return &nodes[szn++];
}
tree copy(tree v) {
if(v == nullptr) return v;
return getNode(v->line, v->l, v->r);
}
li f(const pt &line, int x) {
return line * pt{x, 1};
}
tree addLine(tree v, int l, int r, pt line) {
if(!v)
return getNode(line, nullptr, nullptr);
int mid = (l + r) >> 1;
bool lf = f(line, l) < f(v->line, l);
bool md = f(line, mid) < f(v->line, mid);
if(md)
swap(v->line, line);
if(l + 1 == r)
return v;
else if(lf != md)
v->l = addLine(copy(v->l), l, mid, line);
else
v->r = addLine(copy(v->r), mid, r, line);
return v;
}
li getMin(tree v, int l, int r, int x) {
if(!v) return INF64;
if(l + 1 == r)
return f(v->line, x);
int mid = (l + r) >> 1;
if(x < mid)
return min(f(v->line, x), getMin(v->l, l, mid, x));
else
return min(f(v->line, x), getMin(v->r, mid, r, x));
}
int n, k;
vector<li> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
struct state {
int pos;
pHull hull;
tree v;
state() : pos(-1), hull(nullptr), v(nullptr) {}
};
vector<li> d[2];
inline void solve() {
int maxn = (int)*max_element(a.begin(), a.end()) + 3;
fore(k, 0, 2)
d[k].resize(n + 1, INF64);
d[0][0] = 0;
fore(_k, 1, k + 1) {
szn = 0;
int ck = _k & 1;
int nk = ck ^ 1;
vector< state > st;
fore(i, 0, sz(d[ck])) {
d[ck][i] = INF64;
if(!st.empty())
d[ck][i] = getMin(st.back().v, 0, maxn, i);
if(i >= sz(a))
continue;
state curVal;
curVal.pos = i;
curVal.hull = make_unique<LinearHull>();
curVal.hull->addRight({-i, d[nk][i]});
curVal.v = nullptr;
while(!st.empty() && a[st.back().pos] < a[i]) {
mergeHulls(st.back().hull, curVal.hull);
st.pop_back();
}
if(!st.empty())
curVal.v = st.back().v;
li val = curVal.hull->getMin({a[i], 1});
curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val});
st.push_back(move(curVal));
}
}
cout << d[k & 1][n] << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}