QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#449850 | #8597. Запити красот пiдмасивiв | green_gold_dog# | 0 | 910ms | 349800kb | C++20 | 6.8kb | 2024-06-21 18:17:42 | 2024-06-21 18:17:43 |
Judging History
answer
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 21;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
struct segment_tree_min {
vector<pair<ll, ll>> tree;
vector<ll> m;
ll size;
segment_tree_min(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
tree.resize(size * 2, make_pair(0, 0));
m.resize(size * 2, 0);
for (ll i = 0; i < size; i++) {
tree[i + size].second = i;
}
}
pair<ll, ll> add(ll v, ll x) {
tree[v].first += x;
m[v] += x;
return tree[v];
}
void push(ll v) {
add(v * 2, m[v]);
add(v * 2 + 1, m[v]);
m[v] = 0;
}
void add(ll l, ll r, ll x) {
add(1, 0, size, l, r, x);
}
pair<ll, ll> add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
return add(v, x);
}
if (qr <= l || r <= ql) {
return tree[v];
}
push(v);
ll mid = (l + r) / 2;
return tree[v] = min(add(v * 2, l, mid, ql, qr, x), add(v * 2 + 1, mid, r, ql, qr, x));
}
pair<ll, ll> get(ll l, ll r) {
return get(1, 0, size, l, r);
}
pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
if (ql <= l && r <= qr) {
return tree[v];
}
if (qr <= l || r <= ql) {
return make_pair(INF64, 0);
}
push(v);
ll mid = (l + r) / 2;
return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
}
};
struct segment_tree_max {
vector<pair<ll, ll>> tree;
vector<ll> m;
ll size;
segment_tree_max(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
tree.resize(size * 2, make_pair(0, 0));
m.resize(size * 2, 0);
for (ll i = 0; i < size; i++) {
tree[i + size].second = i;
}
}
pair<ll, ll> add(ll v, ll x) {
tree[v].first += x;
m[v] += x;
return tree[v];
}
void push(ll v) {
add(v * 2, m[v]);
add(v * 2 + 1, m[v]);
m[v] = 0;
}
void add(ll l, ll r, ll x) {
add(1, 0, size, l, r, x);
}
pair<ll, ll> add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
return add(v, x);
}
if (qr <= l || r <= ql) {
return tree[v];
}
push(v);
ll mid = (l + r) / 2;
return tree[v] = max(add(v * 2, l, mid, ql, qr, x), add(v * 2 + 1, mid, r, ql, qr, x));
}
pair<ll, ll> get(ll l, ll r) {
return get(1, 0, size, l, r);
}
pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
if (ql <= l && r <= qr) {
return tree[v];
}
if (qr <= l || r <= ql) {
return make_pair(-INF64, 0);
}
push(v);
ll mid = (l + r) / 2;
return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
}
};
void solve() {
ll n, q;
cin >> n >> q;
vector<ll> arr(n);
vector<ll> ps(1, 0);
for (ll i = 0; i < n; i++) {
cin >> arr[i];
}
reverse(arr.begin(), arr.end());
for (ll i = 0; i < n; i++) {
ps.push_back(ps.back() + arr[i]);
}
segment_tree_min stmi(n);
segment_tree_max stma(n);
vector<pair<ll, ll>> jmi(n), jma(n);
vector<vector<ll>> pbinup(n + 1, vector<ll>(LOG, n));
vector<vector<ll>> pbinupc(n + 1, vector<ll>(LOG, INF64));
vector<vector<ll>> pbinupminp(n + 1, vector<ll>(LOG, INF64));
vector<vector<ll>> pbinupmaxp(n + 1, vector<ll>(LOG, -INF64));
vector<vector<ll>> mbinup(n + 1, vector<ll>(LOG, n));
vector<vector<ll>> mbinupc(n + 1, vector<ll>(LOG, INF64));
vector<vector<ll>> mbinupminp(n + 1, vector<ll>(LOG, INF64));
vector<vector<ll>> mbinupmaxp(n + 1, vector<ll>(LOG, -INF64));
for (ll i = n - 1; i >= 0; i--) {
stmi.add(i, n, arr[i]);
stma.add(i, n, arr[i]);
jmi[i] = stmi.get(i, n);
jma[i] = stma.get(i, n);
jmi[i].second++;
jma[i].second++;
pbinup[i][0] = jma[i].second;
pbinupc[i][0] = jma[i].first;
pbinupminp[i][0] = ps[i];
pbinupmaxp[i][0] = ps[pbinup[i][0]];
mbinup[i][0] = jmi[i].second;
mbinupc[i][0] = -jmi[i].first;
mbinupmaxp[i][0] = ps[i];
mbinupminp[i][0] = ps[mbinup[i][0]];
{
ll j = 1;
pbinup[i][j] = mbinup[pbinup[i][j - 1]][j - 1];
pbinupc[i][j] = min(mbinupc[pbinup[i][j - 1]][j - 1], pbinupc[i][j - 1]);
pbinupminp[i][j] = min(mbinupminp[pbinup[i][j - 1]][j - 1], pbinupminp[i][j - 1]);
pbinupmaxp[i][j] = max(mbinupmaxp[pbinup[i][j - 1]][j - 1], pbinupmaxp[i][j - 1]);
mbinup[i][j] = pbinup[mbinup[i][j - 1]][j - 1];
mbinupc[i][j] = min(pbinupc[mbinup[i][j - 1]][j - 1], mbinupc[i][j - 1]);
mbinupminp[i][j] = min(pbinupminp[mbinup[i][j - 1]][j - 1], mbinupminp[i][j - 1]);
mbinupmaxp[i][j] = max(pbinupmaxp[mbinup[i][j - 1]][j - 1], mbinupmaxp[i][j - 1]);
}
for (ll j = 2; j < LOG; j++) {
pbinup[i][j] = pbinup[pbinup[i][j - 1]][j - 1];
pbinupc[i][j] = min(pbinupc[pbinup[i][j - 1]][j - 1], pbinupc[i][j - 1]);
pbinupminp[i][j] = min(pbinupminp[pbinup[i][j - 1]][j - 1], pbinupminp[i][j - 1]);
pbinupmaxp[i][j] = max(pbinupmaxp[pbinup[i][j - 1]][j - 1], pbinupmaxp[i][j - 1]);
mbinup[i][j] = mbinup[mbinup[i][j - 1]][j - 1];
mbinupc[i][j] = min(mbinupc[mbinup[i][j - 1]][j - 1], mbinupc[i][j - 1]);
mbinupminp[i][j] = min(mbinupminp[mbinup[i][j - 1]][j - 1], mbinupminp[i][j - 1]);
mbinupmaxp[i][j] = max(mbinupmaxp[mbinup[i][j - 1]][j - 1], mbinupmaxp[i][j - 1]);
}
}
for (ll i = 0; i < q; i++) {
ll t, l, r;
cin >> t >> l >> r;
if (t == 1) {
r = n - r;
l = n - l;
l++;
swap(l, r);
ll nl = 0, nr = INF64;
while (nr - nl > 1) {
ll mid = (nl + nr) / 2;
ll vm = l, vp = l;
ll mminp = ps[l], mmaxp = ps[l];
ll pminp = ps[l], pmaxp = ps[l];
for (ll j = LOG - 1; j >= 0; j--) {
if (mbinup[vm][j] < r && mbinupc[vm][j] >= mid) {
assign_min(mminp, mbinupminp[vm][j]);
assign_max(mmaxp, mbinupmaxp[vm][j]);
vm = mbinup[vm][j];
}
if (pbinup[vp][j] < r && pbinupc[vp][j] >= mid) {
assign_min(pminp, pbinupminp[vp][j]);
assign_max(pmaxp, pbinupmaxp[vp][j]);
vp = pbinup[vp][j];
}
}
if (max(max(ps[r] - mminp, mmaxp - ps[r]), max(ps[r] - pminp, pmaxp - ps[r])) >= mid) {
nl = mid;
} else {
nr = mid;
}
}
cout << nl << '\n';
} else {
exit(1);
}
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1000000 1000000 548734664 631285694 511074814 185066089 177199147 524740185 143108778 954318193 103939390 194933972 126964310 977448144 188825490 775722231 460775045 254691982 436971964 566341931 148211711 74910105 923734998 440021758 474275150 717904448 680353276 612974499 712145218 300908726 34722...
output:
251801387395338 230985543990378 233364582761908 165509624203582 383254838720986 448483728625094 365779189638223 259921744673457 396032911262151 463175787332481 396490494773605 379294045009719 380905359946099 248640668979163 372751657582612 250611799614193 382671202614963 249747705028859 377678676465...
result:
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 4ms
memory: 5240kb
input:
1000 1000 -873807720 -737050877 797489760 406646247 -750849890 -581119106 43724194 -931326234 -9389547 -684003608 -926307185 -502569356 -461635706 -238087464 -83909772 -884633970 46721429 -576741985 -323890970 -855342249 -736506813 336516318 -4075924 -782227362 56799828 290931118 -471600723 81594380...
output:
9772834244 2003856312 7251185652 2554989078 12301584130 9137214347 10770040139 9693548841 12636393268 9951777555 8590138425 9126178404 8438322412 10469973494 9585010202 12336530829 12305905331 12818655084 9576894451 9228532410 10060968297 12060843219 8619457836 8862797014 12336530829 6408306273 9621...
result:
wrong answer 2nd numbers differ - expected: '7971661681', found: '2003856312'
Subtask #3:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 910ms
memory: 349736kb
input:
200000 200000 580139218 -783262026 565291185 -701435432 -591602198 -342573855 -900284959 -10919966 -682899137 -282058183 963121871 491072571 691886927 761414760 -828585515 888361166 -790814084 145385324 214735368 388759807 -80339362 -975535748 522135695 301673442 36714481 785639770 319723485 1098009...
output:
351460487491 210343422436 312498498649 203192986383 287815765786 245818714404 213968420688 159327542896 169009698075 212975612931 197610853645 255310400798 318802499824 292657635865 313528174745 321957839407 262317902055 187559666100 220264896012 221468083688 294234309666 310907237863 189575747002 1...
result:
wrong answer 52nd numbers differ - expected: '123800915687', found: '82061951235'
Subtask #4:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 817ms
memory: 349800kb
input:
200000 200000 128744308 920701830 -482412021 59142239 721167306 -622861403 165749748 -449445968 -760679479 -207234657 171482190 -239316743 75518499 -717652242 502074875 -731242646 -183939818 -625333917 -53052313 185734819 -780000096 -563390882 -690210905 596581513 764466021 776717157 -38544163 -7898...
output:
128744308 1049446138 567034117 626176356 1347343662 724482259 890232007 906557623 1347343662 1347343662 1347343662 1347343662 1347343662 1347343662 1347343662 1466264164 1650203982 2275537899 2328590212 2142855393 2922855489 3486246371 4176457276 3579875763 2815409742 2137764691 2099220528 286704480...
result:
wrong answer 71st numbers differ - expected: '3002133635', found: '2435794510'
Subtask #5:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 870ms
memory: 349648kb
input:
200000 200000 3 -5 -3 3 3 -5 7 -2 2 -4 -4 9 0 -4 -2 2 -5 7 -2 3 -8 1 6 -7 9 -3 -2 4 -2 -2 3 -2 1 0 -3 6 0 -6 -2 6 -5 6 -4 3 2 -4 5 -2 -8 1 1 2 1 -3 3 5 -9 1 3 -2 0 1 -2 1 2 5 -1 -4 -1 -3 7 -7 7 1 -6 7 -1 -5 1 4 -7 6 -3 -4 -1 4 1 5 -7 -3 9 1 -6 2 -3 1 6 -1 -1 1 -1 -5 -3 9 -5 4 -1 3 -2 -4 -4 8 1 0 -9 ...
output:
1 7 8 6 8 4 3 7 9 9 5 9 6 6 9 3 8 1 8 3 6 6 4 7 6 4 3 2 8 5 6 3 5 5 3 7 5 1 7 5 9 5 8 0 5 7 6 8 5 5 6 2 3 6 6 8 4 6 9 4 6 3 6 5 8 6 6 5 5 9 8 4 7 6 4 5 6 2 3 7 4 5 4 4 6 7 9 1 2 9 3 4 5 1 9 3 2 4 9 4 7 2 9 7 8 1 8 8 5 6 8 8 3 6 5 3 6 5 9 6 6 8 1 5 8 4 5 3 7 4 10 2 5 5 6 8 2 2 6 4 6 8 6 5 0 8 7 2 3 7...
result:
wrong answer 1st numbers differ - expected: '9', found: '1'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%