# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
199551 | 2020-02-02T02:32:01 Z | arnold518 | 역사적 조사 (JOI14_historical) | C++14 | 12 ms | 1144 KB |
#pragma GCC optimize ("O3") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const int SQ = 500; int N, Q, A[MAXN+10], B[MAXN+10], S; vector<int> comp; struct Query { int l, r, p; bool operator < (const Query &p) { if(l/SQ==p.l/SQ) return r<p.r; return l<p.l; } }; Query query[MAXN+10]; ll tree[MAXN*4+10], ans[MAXN+10]; void update(int node, int tl, int tr, int pos, ll val) { while(tl!=tr) { int mid=tl+tr>>1; if(pos<=mid) node=node*2, tr=mid; else node=node*2+1, tl=mid+1; } tree[node]+=val; while(node!=1) { node<<=1; tree[node]=max(tree[node*2], tree[node*2+1]); } } ll qquery() { return tree[1]; } void push(int x) { update(1, 1, S, B[x], A[x]); } void pop(int x) { update(1, 1, S, B[x], -A[x]); } int main() { int i, j; scanf("%d%d", &N, &Q); for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]); sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); S=comp.size(); for(i=1; i<=N; i++) B[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1; for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i; sort(query+1, query+Q+1); int l=1, r=1; push(1); for(i=1; i<=Q; i++) { while(r<query[i].r) r++, push(r); while(l>query[i].l) l--, push(l); while(r>query[i].r) pop(r), r--; while(l<query[i].l) pop(l), l++; ans[query[i].p]=qquery(); } for(i=1; i<=Q; i++) printf("%lld\n", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 1144 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |