# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
290075 |
2020-09-03T11:16:21 Z |
balbit |
Triple Jump (JOI19_jumps) |
C++14 |
|
1574 ms |
131992 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e5+5;
struct RMQ{
int seg[2 * maxn];
void build() { // build the tree
for (int i = maxn - 1; i > 0; --i) seg[i] = max(seg[i<<1] , seg[i<<1|1]);
}
void modify(int p, int value) { // set value at position p
for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
}
int query(int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res, seg[l++]);
if (r&1) res = max(res, seg[--r]);
}
return res;
}
RMQ(){
memset(seg, 0, sizeof seg);
}
};
int a[maxn];
struct EV{
int l, r, v;
};
struct QUE{
int l,r,i;
};
RMQ ar, dp;
struct QQ{
int i, v, mx;
bool operator < (const QQ &b) const {return i!=b.i?i<b.i:v>b.v;}
};
vector<QQ> here [maxn];
ll bg[maxn];
set<QQ> nowqq;
void upd(int i) {
for (QQ x : here[i]) {
// add x
if (x.v > bg[x.i]) {
bg[x.i] = x.v;
}else continue;
auto it = nowqq.insert(x).f;
bug("HI");
if (it != nowqq.begin() && prev(it)->v >= x.v) {
nowqq.erase(it); continue;
}
if (it != nowqq.begin()) {
dp.modify(prev(it)->i, prev(it) -> v + ar.query(prev(it)->i, x.i));
}
bug("HI");
it = next(it);
while (it->v <= x.v){
dp.modify(it->i, 0);
it = nowqq.erase(it);
}
bug("HI");
x.mx = ar.query(x.i, it->i);
dp.modify(x.i, x.v + x.mx);
bug("HI");
}
}
ll QU(int i) {
auto fs = prev(nowqq.upper_bound({i, -1, 0}));
ll re = ar.query(fs->i, i+1) + fs->v; // inclusive
re = max(re, dp.query(0, fs->i));
return re;
}
signed main(){
IOS();
int n; cin>>n;
vector<EV> lines;
{
vector<pii> tt;
for (int i = 0; i<n; ++i) {
cin>>a[i]; tt.pb({-a[i],i}); ar.modify(i,a[i]);
}
sort(ALL(tt));
set<int> tmps;
for (auto & p : tt) {
int i = p.s;
auto it = tmps.insert(i).f;
if (i != *tmps.rbegin()) {
int j = *next(it);
lines.pb({i, j + j-i, a[i] + a[j]});
}
if (i != *tmps.begin()) {
int j = *prev(it);
lines.pb({j, i + i-j, a[i] + a[j]});
}
}
// return 0;
}
// for (auto & l : lines) {bug(l.l, l.r, l.v);}
// lines.clear();
// for (int i = 0; i<n; ++i) for (int j = i+1; j<n; ++j) lines.pb({i,j-i+j,a[i] + a[j]});
for (auto xx : lines) {
if (xx.r < n)
here[xx.l] . pb({xx.r, xx.v, -1});
}
// return 0;
int numq; cin>>numq;
vector<QUE> qlist;
for (int i = 0; i<numq; ++i) {
int l,r; cin>>l>>r;
qlist.pb({l-1,r-1,i});
}
nowqq.insert({n,1000000000,0});
sort(ALL(qlist),[&](QUE a, QUE b){return a.l > b.l;});
int nowl = n;
vector<int> ans(numq);
// return 0;
for (QUE q : qlist) {
bug(q.l);
while (nowl > q.l) {
upd(--nowl);
}
ans[q.i] = QU(q.r);
}
for (int x : ans) {
cout<<x<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
27900 KB |
Output is correct |
2 |
Correct |
18 ms |
27776 KB |
Output is correct |
3 |
Correct |
18 ms |
27776 KB |
Output is correct |
4 |
Correct |
20 ms |
27776 KB |
Output is correct |
5 |
Correct |
17 ms |
27776 KB |
Output is correct |
6 |
Correct |
20 ms |
27776 KB |
Output is correct |
7 |
Correct |
18 ms |
27776 KB |
Output is correct |
8 |
Correct |
18 ms |
27776 KB |
Output is correct |
9 |
Correct |
18 ms |
27776 KB |
Output is correct |
10 |
Correct |
18 ms |
27776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
27900 KB |
Output is correct |
2 |
Correct |
18 ms |
27776 KB |
Output is correct |
3 |
Correct |
18 ms |
27776 KB |
Output is correct |
4 |
Correct |
20 ms |
27776 KB |
Output is correct |
5 |
Correct |
17 ms |
27776 KB |
Output is correct |
6 |
Correct |
20 ms |
27776 KB |
Output is correct |
7 |
Correct |
18 ms |
27776 KB |
Output is correct |
8 |
Correct |
18 ms |
27776 KB |
Output is correct |
9 |
Correct |
18 ms |
27776 KB |
Output is correct |
10 |
Correct |
18 ms |
27776 KB |
Output is correct |
11 |
Correct |
278 ms |
49468 KB |
Output is correct |
12 |
Correct |
302 ms |
49496 KB |
Output is correct |
13 |
Correct |
270 ms |
49112 KB |
Output is correct |
14 |
Correct |
279 ms |
49288 KB |
Output is correct |
15 |
Correct |
261 ms |
49420 KB |
Output is correct |
16 |
Correct |
260 ms |
48652 KB |
Output is correct |
17 |
Correct |
263 ms |
48632 KB |
Output is correct |
18 |
Correct |
255 ms |
48652 KB |
Output is correct |
19 |
Correct |
262 ms |
49036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
411 ms |
54404 KB |
Output is correct |
2 |
Correct |
170 ms |
56084 KB |
Output is correct |
3 |
Correct |
147 ms |
48252 KB |
Output is correct |
4 |
Correct |
411 ms |
55072 KB |
Output is correct |
5 |
Correct |
418 ms |
55300 KB |
Output is correct |
6 |
Correct |
307 ms |
54404 KB |
Output is correct |
7 |
Correct |
317 ms |
54276 KB |
Output is correct |
8 |
Correct |
315 ms |
54352 KB |
Output is correct |
9 |
Correct |
308 ms |
54660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
27900 KB |
Output is correct |
2 |
Correct |
18 ms |
27776 KB |
Output is correct |
3 |
Correct |
18 ms |
27776 KB |
Output is correct |
4 |
Correct |
20 ms |
27776 KB |
Output is correct |
5 |
Correct |
17 ms |
27776 KB |
Output is correct |
6 |
Correct |
20 ms |
27776 KB |
Output is correct |
7 |
Correct |
18 ms |
27776 KB |
Output is correct |
8 |
Correct |
18 ms |
27776 KB |
Output is correct |
9 |
Correct |
18 ms |
27776 KB |
Output is correct |
10 |
Correct |
18 ms |
27776 KB |
Output is correct |
11 |
Correct |
278 ms |
49468 KB |
Output is correct |
12 |
Correct |
302 ms |
49496 KB |
Output is correct |
13 |
Correct |
270 ms |
49112 KB |
Output is correct |
14 |
Correct |
279 ms |
49288 KB |
Output is correct |
15 |
Correct |
261 ms |
49420 KB |
Output is correct |
16 |
Correct |
260 ms |
48652 KB |
Output is correct |
17 |
Correct |
263 ms |
48632 KB |
Output is correct |
18 |
Correct |
255 ms |
48652 KB |
Output is correct |
19 |
Correct |
262 ms |
49036 KB |
Output is correct |
20 |
Correct |
411 ms |
54404 KB |
Output is correct |
21 |
Correct |
170 ms |
56084 KB |
Output is correct |
22 |
Correct |
147 ms |
48252 KB |
Output is correct |
23 |
Correct |
411 ms |
55072 KB |
Output is correct |
24 |
Correct |
418 ms |
55300 KB |
Output is correct |
25 |
Correct |
307 ms |
54404 KB |
Output is correct |
26 |
Correct |
317 ms |
54276 KB |
Output is correct |
27 |
Correct |
315 ms |
54352 KB |
Output is correct |
28 |
Correct |
308 ms |
54660 KB |
Output is correct |
29 |
Correct |
1566 ms |
131724 KB |
Output is correct |
30 |
Correct |
1326 ms |
125992 KB |
Output is correct |
31 |
Correct |
750 ms |
104644 KB |
Output is correct |
32 |
Correct |
1574 ms |
131808 KB |
Output is correct |
33 |
Correct |
1569 ms |
131820 KB |
Output is correct |
34 |
Correct |
1260 ms |
129632 KB |
Output is correct |
35 |
Correct |
1265 ms |
129168 KB |
Output is correct |
36 |
Correct |
1259 ms |
129340 KB |
Output is correct |
37 |
Correct |
1273 ms |
130828 KB |
Output is correct |
38 |
Correct |
1504 ms |
131992 KB |
Output is correct |
39 |
Correct |
1482 ms |
131856 KB |
Output is correct |
40 |
Correct |
1150 ms |
128520 KB |
Output is correct |
41 |
Correct |
1188 ms |
128208 KB |
Output is correct |
42 |
Correct |
1166 ms |
128052 KB |
Output is correct |
43 |
Correct |
1178 ms |
129804 KB |
Output is correct |
44 |
Correct |
1468 ms |
131876 KB |
Output is correct |
45 |
Correct |
1471 ms |
131884 KB |
Output is correct |
46 |
Correct |
1151 ms |
128780 KB |
Output is correct |
47 |
Correct |
1151 ms |
128268 KB |
Output is correct |
48 |
Correct |
1148 ms |
128276 KB |
Output is correct |
49 |
Correct |
1190 ms |
130388 KB |
Output is correct |
50 |
Correct |
1496 ms |
131852 KB |
Output is correct |
51 |
Correct |
1508 ms |
131912 KB |
Output is correct |
52 |
Correct |
1177 ms |
129740 KB |
Output is correct |
53 |
Correct |
1189 ms |
129012 KB |
Output is correct |
54 |
Correct |
1208 ms |
129136 KB |
Output is correct |
55 |
Correct |
1192 ms |
130716 KB |
Output is correct |