# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
944151 | 2024-03-12T09:07:57 Z | beepbeepsheep | 3단 점프 (JOI19_jumps) | C++17 | 3918 ms | 524288 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define ii pair<ll,ll> #ifndef DEBUG #define cerr if (0) cerr #define endl '\n' #endif const ll maxn=5005; const ll inf=1e15; ll arr[maxn]; struct node{ ll s,e,m,val; node *l,*r; node (ll _s, ll _e){ s=_s,e=_e,m=(s+e)>>1,val=0; if (s!=e) l=new node(s,m),r=new node(m+1,e); } void upd(ll x, ll v){ if (s==e){ val=max(v,val); return; } if (x>m) r->upd(x,v); else l->upd(x,v); val=max(l->val,r->val); } ll query(ll x, ll y){ if (x<=s && e<=y) return val; if (x>m) return r->query(x,y); if (y<=m) return l->query(x,y); return max(l->query(x,y),r->query(x,y)); } }*root,*rmq; ll n; vector<tuple<ll,ll,ll>> v,q; ll ans[maxn]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; root=new node(1,n); for (int i=1;i<=n;i++) cin>>arr[i],root->upd(i,arr[i]); for (int i=1;i<=n;i++){ for (int j=i+2;j<=n;j++){ v.emplace_back(i,j,arr[i]+arr[j]+ root->query(i+1,(i+j)>>1)); //cerr<<i<<' '<<j<<' '<<arr[i]+arr[j]+root->query(i+1,(i+j)>>1)<<endl; } } sort(v.rbegin(),v.rend()); rmq=new node(1,n); ll qu,l,r; cin>>qu; for (int i=1;i<=qu;i++){ cin>>l>>r; q.emplace_back(l,r,i); } sort(q.rbegin(),q.rend()); ll ptr=0; for (auto [l,r,i]:q){ while (ptr!=v.size() && l<=get<0>(v[ptr])){ rmq->upd(get<1>(v[ptr]),get<2>(v[ptr])); ptr++; } ans[i]=rmq->query(l,r); } for (int i=1;i<=qu;i++){ cout<<ans[i]<<endl; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 1 ms | 856 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 1 ms | 856 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Runtime error | 3918 ms | 524288 KB | Execution killed with signal 9 |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 47 ms | 51220 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 1 ms | 856 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 1 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Runtime error | 3918 ms | 524288 KB | Execution killed with signal 9 |
12 | Halted | 0 ms | 0 KB | - |