Submission #593409

#TimeUsernameProblemLanguageResultExecution timeMemory
593409haojiandanTriple Jump (JOI19_jumps)C++14
100 / 100
877 ms110348 KiB
// wygzgyw #include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } template <typename T> void write(T t) { if (t<0) { putchar('-'); write(-t); return; } if (t>9) write(t/10); putchar('0'+t%10); } template <typename T> void writeln(T t) { write(t); puts(""); } #define MP make_pair typedef long long ll; const ll INF=1e10; const int maxn=(5e5)+10; int n,a[maxn]; int q,st[maxn],tot; struct node { int r,id; }; vector<int> A[maxn]; vector<node> g[maxn]; ll ans[maxn]; namespace Seg { ll mx[maxn*4],tr[maxn*4],MX[maxn*4]; ll lazy[maxn*4]; void pushup(int root) { tr[root]=max(tr[root<<1],tr[root<<1|1]); mx[root]=max(mx[root<<1],mx[root<<1|1]); MX[root]=max(MX[root<<1],MX[root<<1|1]); } void build(int l,int r,int root) { tr[root]=mx[root]=lazy[root]=-INF; if (l==r) { MX[root]=a[l]; return; } int mid=(l+r)>>1; build(l,mid,root<<1),build(mid+1,r,root<<1|1); pushup(root); } void puttag(int root,ll delta) { tr[root]=delta+MX[root],mx[root]=lazy[root]=delta; } void pushdown(int root) { if (lazy[root]!=-INF) puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=-INF; } void update(int L,int R,int l,int r,int root,ll delta) { if (L>R) return; if (L<=l&&r<=R) { puttag(root,delta); return; } int mid=(l+r)>>1; pushdown(root); if (L<=mid) update(L,R,l,mid,root<<1,delta); if (mid<R) update(L,R,mid+1,r,root<<1|1,delta); pushup(root); } int query(int L,int R,int l,int r,int root,ll delta) { if (mx[root]<=delta) return n+1; if (L<=l&&r<=R) { if (l==r) return l; int mid=(l+r)>>1; pushdown(root); if (mx[root<<1]>delta) return query(L,R,l,mid,root<<1,delta); return query(L,R,mid+1,r,root<<1|1,delta); } int mid=(l+r)>>1; pushdown(root); int res=n+1; if (L<=mid) { res=query(L,R,l,mid,root<<1,delta); if (res!=n+1) return res; } if (mid<R) res=query(L,R,mid+1,r,root<<1|1,delta); return res; } ll query(int L,int R,int l,int r,int root) { if (L<=l&&r<=R) return tr[root]; int mid=(l+r)>>1; pushdown(root); ll res=-INF; if (L<=mid) res=max(res,query(L,R,l,mid,root<<1)); if (mid<R) res=max(res,query(L,R,mid+1,r,root<<1|1)); return res; } }; int main() { //freopen("1.txt","r",stdin); read(n); for (int i=1;i<=n;i++) read(a[i]); for (int i=1;i<=n;i++) { while (tot&&a[st[tot]]<a[i]) tot--; if (tot) A[st[tot]].push_back(i); st[++tot]=i; } tot=0; for (int i=n;i>=1;i--) { while (tot&&a[st[tot]]<a[i]) tot--; if (tot) A[i].push_back(st[tot]); st[++tot]=i; } read(q); for (int i=1;i<=q;i++) { int x,y; read(x),read(y); g[x].push_back((node){y,i}); } Seg::build(1,n,1); for (int i=n;i>=1;i--) { for (int &j : A[i]) if (j*2-i<=n) { // printf("i=%d,j=%d\n",i,j); int R=Seg::query(j*2-i,n,1,n,1,a[i]+a[j])-1; Seg::update(j*2-i,R,1,n,1,a[i]+a[j]); } for (node &A : g[i]) { ans[A.id]=Seg::query(1,A.r,1,n,1); } } for (int i=1;i<=q;i++) printf("%lld\n",ans[i]); return 0; } /* 0. Enough array size? Enough array size? Enough array size? Integer overflow? 1. Think TWICE, Code ONCE! Are there any counterexamples to your algo? 2. Be careful about the BOUNDARIES! N=1? P=1? Something about 0? 3. Do not make STUPID MISTAKES! Time complexity? Memory usage? Precision error? */

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:89:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   89 |   if (tot) A[st[tot]].push_back(i); st[++tot]=i;
      |   ^~
jumps.cpp:89:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   89 |   if (tot) A[st[tot]].push_back(i); st[++tot]=i;
      |                                     ^~
jumps.cpp:94:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   94 |   if (tot) A[i].push_back(st[tot]); st[++tot]=i;
      |   ^~
jumps.cpp:94:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   94 |   if (tot) A[i].push_back(st[tot]); st[++tot]=i;
      |                                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...