IN C++
TEST - 35
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve()
{
ll N,M;
ll x,prefix=0,maxim=0;
cin>>N>>M;
set<ll> S;
S.insert(0);
for(int i=1;i<=N;i++){
cin>>x;
prefix = (prefix + x)%M;
maxim = max(maxim,prefix);
set<ll>::iterator it = S.lower_bound(prefix+1);
if( it != S.end() ){
maxim = max(maxim,prefix - (*it) + M );
}
S.insert(prefix);
}
cout<<maxim<<endl;
}
int main()
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Maximizing Mission Points
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const N = 800600;
ll const INFL = 1e18 + 111;
struct Item {
int x, y, h;
ll cost;
};
struct Max {
vector<pair<ll, ll>> a, b;
Max() {
clear();
}
void clear() {
a.clear();
a.emplace_back(-INFL, -INFL);
b.clear();
b.emplace_back(-INFL, -INFL);
}
void add(ll x) {
a.emplace_back(x, max(a.back().second, x));
}
ll get_max() const {
return max(a.back().second, b.back().second);
}
void pop() {
if (b.size() == 1u) {
while (a.size() > 1u) {
b.emplace_back(a.back().first, max(a.back().first, b.back().second));
a.pop_back();
}
}
b.pop_back();
assert(a.size() >= 1u);
assert(b.size() >= 1u);
}
};
int n, dx, dy;
Item items[N];
ll ans[N];
Max leafs[N];
ll tree[N];
void build(int v, int l, int r) {
tree[v] = -INFL;
if (r - l > 1) {
int m = (l + r) / 2;
build(2 * v + 1, l, m);
build(2 * v + 2, m, r);
} else {
leafs[l].clear();
}
}
void add_number(int v, int l, int r, int pos, ll num) {
if (r - l == 1) {
if (num == INFL)
leafs[l].pop();
else
leafs[l].add(num);
tree[v] = leafs[l].get_max();
} else {
int m = (l + r) / 2;
if (pos < m)
add_number(2 * v + 1, l, m, pos, num);
else
add_number(2 * v + 2, m, r, pos, num);
tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}
}
ll get_max(int v, int l, int r, int from, int to) {
if (r <= from || to <= l)
return -INFL;
if (from <= l && r <= to)
return tree[v];
int m = (l + r) / 2;
return max(get_max(2 * v + 1, l, m, from, to), get_max(2 * v + 2, m, r, from, to));
}
struct Event {
int x, y1, y2, type, i; /// -1 - open, 0 - point, 1 - close
};
bool operator<(Event const& e1, Event const& e2) {
if (e1.x != e2.x)
return e1.x < e2.x;
return e1.type < e2.type;
}
void go(int L, int R) {
if (R - L == 1) {
} else {
int M = (L + R) / 2;
go(L, M);
static int ally[N];
int cn = 0;
for (int i = L; i < M; ++i) {
ally[cn++] = items[i].y;
}
sort(ally, ally + cn);
cn = unique(ally, ally + cn) - ally;
#define comp(q) (lower_bound(ally, ally + cn, q) - ally)
static Event events[N];
int es = 0;
for (int i = L; i < M; ++i) {
int q = comp(items[i].y);
events[es++] = {items[i].x - dx, q, -1, -1, i};
events[es++] = {items[i].x + dx, q, -1, 1, i};
}
for (int i = M; i < R; ++i) {
int from = comp(items[i].y - dy);
int to = comp(items[i].y + dy + 1);
events[es++] = {items[i].x, from, to, 0, i};
}
build(0, 0, cn);
sort(events, events + es);
for (int i = 0; i < es; ++i) {
auto e = events[i];
if (e.type == -1) {
add_number(0, 0, cn, e.y1, ans[e.i]);
} else if (e.type == 1) {
add_number(0, 0, cn, e.y1, INFL);
} else {
ll cur = get_max(0, 0, cn, e.y1, e.y2) + items[e.i].cost;
ans[e.i] = max(ans[e.i], cur);
}
}
go(M, R);
}
}
bool solve() {
if (scanf("%d%d%d", &n, &dx, &dy) < 0) {
return false;
}
assert(n >= 1 && n <= 200000);
assert(dx >= 1 && dx <= 200000);
assert(dy >= 1 && dy <= 200000);
for (int i = 0; i < n; ++i) {
int x, y, h, cost;
scanf("%d%d%d%d", &x, &y, &h, &cost);
assert(x >= 1 && x <= 200000);
assert(y >= 1 && y <= 200000);
assert(h >= 1 && h <= 200000);
assert(cost >= -200000 && cost <= 200000);
items[i] = {x, y, h, (ll)cost};
}
sort(items, items + n, [](Item const &a, Item const &b) {
return a.h < b.h;
});
for (int i = 0; i < n; ++i) {
ans[i] = items[i].cost;
}
go(0, n);
ll res = 0;
for (int i = 0; i < n; ++i) {
res = max(res, ans[i]);
}
cout << res << '\n';
return true;
}
int main() {
while (solve());
}
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Making Candies
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll machines, ll workers, ll price, ll target, ll rounds) {
if (machines >= (target+workers-1)/workers) return true;
ll cur = machines*workers;
rounds--;
if (rounds == 0) return false;
while (1) {
ll rem = target - cur;
ll rnds = (rem + machines*workers - 1) / (machines*workers);
if (rnds <= rounds) return true;
if (cur < price) {
rem = price - cur;
rnds = (rem + machines*workers - 1) / (machines*workers);
rounds -= rnds;
if (rounds < 1) return false;
cur += rnds * machines * workers;
}
cur -= price;
if (machines > workers) {
workers++;
} else {
machines++;
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll m, w, p, n;
cin >> m >> w >> p >> n;
ll a = 1, b = 1000000000000LL;
while (a < b) {
ll mid = (a + b) >> 1;
if (check(m, w, p, n, mid)) {
b = mid;
} else {
a = mid + 1;
}
}
cout << a << "\n";
return 0;
}
