Submission #290072

#TimeUsernameProblemLanguageResultExecution timeMemory
290072balbitTriple Jump (JOI19_jumps)C++14
19 / 100
1286 ms496184 KiB
#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 = 1e5+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; } }

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:158:17: warning: unused variable 'l' [-Wunused-variable]
  158 |     for (auto & l : lines) {bug(l.l, l.r, l.v);}
      |                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...