| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 736883 |
2023-05-06T10:09:16 Z |
cig32 |
Holiday (IOI14_holiday) |
C++17 |
|
5000 ms |
28296 KB |
#include"holiday.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct segtree_basic {
struct node {
int lazyval, mi, ma, sum; char lazytag;
int len; // not changing
};
int stok;
vector<node> st;
void bu(int l, int r, int idx) {
st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
st[idx].lazytag = '?';
st[idx].len = r - l + 1;
if(l == r) {
return;
}
int mid = (l + r) >> 1;
bu(l, mid, 2*idx+1);
bu(mid+1, r, 2*idx+2);
}
void push_down(int idx) {
if(st[idx].lazytag == '?') return;
if(st[idx].lazytag == ':') {
st[2*idx+1].lazyval = st[idx].lazyval;
st[2*idx+1].mi = st[idx].lazyval;
st[2*idx+1].ma = st[idx].lazyval;
st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = ':';
st[2*idx+2].lazyval = st[idx].lazyval;
st[2*idx+2].mi = st[idx].lazyval;
st[2*idx+2].ma = st[idx].lazyval;
st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = ':';
}
else {
st[2*idx+1].lazyval += st[idx].lazyval;
st[2*idx+1].mi += st[idx].lazyval;
st[2*idx+1].ma += st[idx].lazyval;
st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
st[2*idx+2].lazyval += st[idx].lazyval;
st[2*idx+2].mi += st[idx].lazyval;
st[2*idx+2].ma += st[idx].lazyval;
st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
}
st[idx].lazytag = '?';
st[idx].lazyval = 0;
}
void push_up(int idx) {
st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
}
void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
if(l <= constl && constr <= r) {
st[idx].lazyval = val;
st[idx].mi = val;
st[idx].ma = val;
st[idx].sum = val * st[idx].len;
st[idx].lazytag = ':';
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
else {
u1(l, r, constl, mid, 2*idx+1, val);
u1(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
if(l <= constl && constr <= r) {
st[idx].lazyval += val;
st[idx].mi += val;
st[idx].ma += val;
st[idx].sum += val * st[idx].len;
st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
else {
u2(l, r, constl, mid, 2*idx+1, val);
u2(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
if(l <= constl && constr <= r) {
if(st[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
else {
int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
if(rchild != -1) return rchild;
return qu7(l, r, constl, mid, 2*idx+1, val);
}
}
public:
void resize(int k) {
st.resize(4*k + 10);
stok = k;
bu(0, k, 0);
}
void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
const int MAXN = 1e5 + 5;
int a[MAXN];
int n_, start_, d_;
int f(int thres) {
int ans = 0;
int n = n_, start = start_, d = d_;
int ps[n+1];
ps[0] = 0;
for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (a[i] >= thres);
int ps2[n+1];
ps2[0] = 0;
for(int i=1; i<=n; i++) ps2[i] = ps2[i-1] + (a[i] >= thres ? a[i] : 0);
segtree_basic stb;
stb.resize(n);
for(int i=1; i<=n; i++) stb.range_assign(i, i, i+ps[i]);
for(int i=max(1ll, start-d); i<=start; i++) {
int x = d - (start-i);
int idx = stb.query_lastAtMost(i, n, x+i+ps[i-1]);
if(idx >= start) ans = max(ans, ps2[idx] - ps2[i-1]);
}
start = n+1 - start;
for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (a[n+1-i] >= thres);
for(int i=1; i<=n; i++) ps2[i] = ps2[i-1] + (a[n+1-i] >= thres ? a[n+1-i] : 0);
for(int i=1; i<=n; i++) stb.range_assign(i, i, i+ps[i]);
for(int i=max(1ll, start-d); i<=start; i++) {
int x = d - (start-i);
int idx = stb.query_lastAtMost(i, n, x+i+ps[i-1]);
if(idx >= start) ans = max(ans, ps2[idx] - ps2[i-1]);
}
return ans;
}
long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
n_ = n;
start_ = start + 1;
d_ = d;
set<int> st;
for(int i=0; i<n; i++) st.insert(attraction[i]);
for(int i=1; i<=n; i++) a[i] = attraction[i-1];
vector<int> vt;
for(int ss: st) vt.push_back(ss);
int m = vt.size();
int ans = 0;
for(int i=0; i<m; i++) ans = max(ans, f(vt[i]));
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
708 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
21940 KB |
Output is correct |
| 2 |
Correct |
76 ms |
21972 KB |
Output is correct |
| 3 |
Correct |
142 ms |
22000 KB |
Output is correct |
| 4 |
Correct |
137 ms |
22000 KB |
Output is correct |
| 5 |
Execution timed out |
5103 ms |
20308 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3699 ms |
1568 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
3563 ms |
1568 KB |
Output is correct |
| 4 |
Correct |
3205 ms |
1496 KB |
Output is correct |
| 5 |
Correct |
2631 ms |
1416 KB |
Output is correct |
| 6 |
Correct |
357 ms |
980 KB |
Output is correct |
| 7 |
Correct |
219 ms |
940 KB |
Output is correct |
| 8 |
Correct |
255 ms |
932 KB |
Output is correct |
| 9 |
Correct |
48 ms |
920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
22696 KB |
Output is correct |
| 2 |
Execution timed out |
5017 ms |
28296 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
