1)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
unsigned long max_sum(
unsigned long *partial_sums,
unsigned long *dest,
unsigned length,
unsigned long target
) {
if (length < 2)
return (*dest = *partial_sums);
unsigned
lower_len = length >> 1,
upper_len = length - lower_len;
unsigned long
lower[lower_len],
upper[upper_len],
max_left = max_sum(partial_sums, lower, lower_len, target),
max_right = max_sum(&partial_sums[lower_len], upper, upper_len, target),
max = max_left > max_right ? max_left : max_right;
unsigned lesser = 0, greater = 0;
while (lesser < lower_len && greater < upper_len)
if (upper[greater] < lower[lesser]) {
*dest = upper[greater++];
unsigned long other_max = (*dest++ - lower[lesser]) + target;
if (other_max > max)
max = other_max;
} else
*dest++ = lower[lesser++];
memcpy(dest, &lower[lesser], (lower_len - lesser) * sizeof(*dest));
memcpy(&dest[lower_len - lesser], &upper[greater], (upper_len - greater) * sizeof(*dest));
return max;
}
int main() {
unsigned length;
unsigned long test_case, limit, index;
static unsigned long
items[100000],
buffer[100001] = {[0] = 0},
*partial_sums = &buffer[1];
for (scanf("%lu", &test_case); test_case--; ) {
scanf("%u", &length);
scanf("%lu", &limit);
for (index = 0; index < length; index++) {
scanf("%lu", &items[index]);
items[index] %= limit;
partial_sums[index] = (items[index] + partial_sums[index - 1ULL]) % limit;
}
// n log n, using partial sums w/ merge sort
// either the max is in the lower, upper, or some where in between.
// find the max of each half,
// using sorted order check if the middle max is greater.
static unsigned long ordered[100000];
unsigned long max = max_sum(partial_sums, ordered, length, limit);
// n^2 using partial sums ...
//unsigned long max = partial_sums[0], chunk, sum, i, j;
//for (i = 0; i < length; i++)
// for (j = i; j < length; j++) {
// sum = partial_sums[j] - partial_sums[i - 1];
// if (sum > limit) // overflow ...
// sum += limit;
// if (sum > max)
// max = sum;
// }
// brute-force n^3, take max(sum of all possible lengths)
//unsigned long max = items[0] % limit, chunk;
//for (index = 1; index < length; index++)
// for (chunk = 0; chunk < length/index; chunk++) {
// unsigned long total = 0, start;
// for (start = chunk * index; start < index; total += items[start++]) ;
// total %= limit;
// if (total > max)
// max = total;
// }
printf("%lu\n", max);
}
return 0;
}
2)
IN C++
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
struct MaxVal {
long long val;
MaxVal() : val(-INFL) {}
explicit MaxVal(long long val) : val(val) {}
MaxVal &operator+=(MaxVal that) {
amax(val, that.val);
return *this;
}
MaxVal operator+(MaxVal that) const {
return MaxVal(*this) += that;
}
};
using Val = long long;
using Sum = MaxVal;
//template<typename Val, typename Sum>
struct GetRangeRangeTree2D {
typedef int Pos;
vector<vector<int> > perms;
vector<Pos> poses;
vector<vector<Sum> > nodes;
vector<vector<int> > rcnts;
int n, log2n;
void init(const vector<Pos> &ys, const Val &v = Val()) {
init(ys, vector<Val>(ys.size(), v));
}
private:
struct IndirectPosCmp {
const vector<Pos> &ys;
IndirectPosCmp(const vector<Pos> &ys_) : ys(ys_) { }
bool operator()(int i, int j) const {
bool a = i >= (int)ys.size(), b = j >= (int)ys.size();
if (a || b) return !a < !b;
else return ys[i] < ys[j];
}
};
public:
void init(const vector<Pos> &ys, const vector<Val> &vals) {
n = 1, log2n = 0; while (n < (int)ys.size()) n *= 2, log2n ++;
nodes.resize(n * 2);
perms.assign(log2n + 1, vector<int>(n));
nodes.assign(log2n + 1, vector<Sum>(n * 2));
rcnts.assign(log2n, vector<int>(n + 1));
vector<int> prev(n), cnt(n);
for (int i = 0; i < n; i ++) {
perms[log2n][i] = i;
nodes[log2n][n + i] = i < (int)ys.size() ? Sum(vals[i]) : Sum();
cnt[i] = i;
}
for (int i = n - 1; i > 0; -- i)
nodes[log2n][i] = nodes[log2n][i * 2] + nodes[log2n][i * 2 + 1];
vector<bool> origin(n);
for (int k = log2n - 1; k >= 0; -- k) {
prev.swap(cnt);
int h = 1 << (log2n - k), h2 = (h - 1) / 2 + 1;
vector<int> &cperms = perms[k];
vector<Sum> &cnodes = nodes[k];
vector<int> &crcnts = rcnts[k];
for (int j = 0; j < n; j += h) {
for (int k = 0; k < h; ++ k)
origin[prev[j + k]] = k >= h / 2;
merge(prev.begin() + j, prev.begin() + j + h / 2
, prev.begin() + j + h / 2, prev.begin() + j + h
, cnt.begin() + j, IndirectPosCmp(ys));
for (int i = 0; i < h; i ++) {
int p = cnt[j + i];
cperms[p] = j + i;
cnodes[j * 2 + h + i] = p < (int)ys.size() ? Sum(vals[p]) : Sum();
crcnts[j + i + 1] = crcnts[j + i] + (origin[p] ? 1 : 0);
}
for (int i = h - 1; i > 0; -- i)
cnodes[j * 2 + i] = cnodes[j * 2 + i * 2] + cnodes[j * 2 + i * 2 + 1];
}
}
poses.resize(n);
for (int i = 0; i < n; ++ i)
poses[perms[0][i]] = i < (int)ys.size() ? ys[i] : -1;
}
Sum getRange(int i1, int j1, Pos i2, Pos j2) const {
if (i1 >= j1 || i2 >= j2) return Sum();
int pL = (int)(lower_bound(poses.begin(), poses.end(), i2) - poses.begin());
int pR = (int)(lower_bound(poses.begin() + pL, poses.end(), j2) - poses.begin());
return getRangeRec(0, 1, 0, i1, j1, i2, j2, pL, pR);
}
void set(int p, const Val &x) {
for (int i = p + n, k = log2n; i > 0; i >>= 1, -- k) {
int h = 1 << (log2n - k), base = (i - (1 << k)) * h;
set1(&nodes[k][base * 2], h, perms[k][p] - base, x);
}
}
private:
inline void set1(Sum *cnodes, int h, int i, const Val &x) const {
cnodes[h + i] = Sum(x);
for (i = (i + h) >> 1; i > 0; i >>= 1)
cnodes[i] = sum1(cnodes, h, i * 2) + sum1(cnodes, h, i * 2 + 1);
}
Sum getRangeRec(int k, int i, int l, int i1, int j1, Pos i2, Pos j2, int pL, int pR) const {
if (pL >= pR) return Sum();
int h = 1 << (log2n - k);
int base = (i - (1 << k)) * h;
if (j1 - i1 == h) {
return getRange1(&nodes[k][base * 2], h, pL, pR);
} else {
int m = l + h / 2;
int qL = rcnts[k][base + pL] - rcnts[k][base];
int qR = rcnts[k][base + pR] - rcnts[k][base];
Sum res = Sum();
if (i1 < m)
res += getRangeRec(k + 1, i * 2, l, i1, min(j1, m), i2, j2, pL - qL, pR - qR);
if (m < j1)
res += getRangeRec(k + 1, i * 2 + 1, m, max(i1, m), j1, i2, j2, qL, qR);
return res;
}
}
inline Sum getRange1(const Sum *cnodes, int h, int i, int j) const {
Sum res = Sum();
for (int l = i + h, r = j + h; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += sum1(cnodes, h, l ++);
if (r & 1) res += sum1(cnodes, h, -- r);
}
return res;
}
inline Sum sum1(const Sum *cnodes, int h, int i) const {
return cnodes[i];
}
};
struct City {
int lat, lon, hei, pts;
};
int main() {
int n; int xDiff; int yDiff;
while (~scanf("%d%d%d", &n, &xDiff, &yDiff)) {
vector<City> cities(n);
rep(i, n) {
int A; int B; int C; int D;
scanf("%d%d%d%d", &A, &B, &C, &D);
cities[i] = { A, B, C, D };
}
sort(cities.begin(), cities.end(), [](City a, City b) {
return a.hei < b.hei;
});
vector<pair<int, int>> xis(n);
rep(i, n)
xis[i] = { cities[i].lat, i };
sort(xis.begin(), xis.end());
vector<int> ys(n);
rep(i, n)
ys[i] = cities[xis[i].second].lon;
vector<long long> values(n);
GetRangeRangeTree2D rt;
rt.init(ys, -INFL);
for (int iL = 0, iR = 0; iL != n; ) {
for (; iR != n && cities[iR].hei == cities[iL].hei; ++ iR) {
const City &c = cities[iR];
int xL = (int)(lower_bound(xis.begin(), xis.end(), make_pair(c.lat - xDiff, -INF)) - xis.begin());
int xR = (int)(upper_bound(xis.begin(), xis.end(), make_pair(c.lat + xDiff, INF)) - xis.begin());
int yL = c.lon - yDiff, yR = c.lon + yDiff + 1;
MaxVal sum = rt.getRange(xL, xR, yL, yR);
values[iR] = max(0LL, sum.val) + c.pts;
}
for (; iL != iR; ++ iL) {
const City &c = cities[iL];
int xi = (int)(lower_bound(xis.begin(), xis.end(), make_pair(c.lat, iL)) - xis.begin());
rt.set(xi, values[iL]);
}
}
long long ans = 0;
rep(i, n)
amax(ans, values[i]);
printf("%lld\n", ans);
}
return 0;
}
Comments :
Post a Comment