# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
191505 | 2020-01-15T03:15:05 Z | sealnot123 | 3단 점프 (JOI19_jumps) | C++14 | 1576 ms | 67188 KB |
#include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 500005; vector<int> Q[N]; int ANS[N], L[N], R[N]; LL seg[4*N], lazy[4*N], MA[4*N], num[N]; vector<int> sta; int n, q; void build(int l = 1, int r = n, int now = 1){ if(l == r){ seg[now] = MA[now] = num[l]; return ; } int m = (l+r)>>1; build(l, m, now<<1); build(m+1, r, now<<1|1); seg[now] = MA[now] = max(MA[now<<1], MA[now<<1|1]); } void push(int l, int r, int now){ if(lazy[now]){ seg[now] = max(seg[now], MA[now] + lazy[now]); if(l!=r){ lazy[now<<1] = max(lazy[now<<1], lazy[now]); lazy[now<<1|1] = max(lazy[now<<1|1], lazy[now]); } lazy[now] = 0; } } void add(int ll, int rr, int v, int l = 1, int r = n, int now = 1){ push(l, r, now); if(ll > rr || l > rr || r < ll) return ; if(l >= ll && r <= rr){ lazy[now] = v; push(l, r, now); return ; } int m = (l+r)>>1; add(ll, rr, v, l, m, now<<1); add(ll, rr, v, m+1, r, now<<1|1); seg[now] = max(seg[now<<1], seg[now<<1|1]); } int get(int ll, int rr, int l = 1, int r = n, int now = 1){ push(l, r, now); if(ll > rr || l > rr || r < ll) return 0; if(l >= ll && r <= rr) return seg[now]; int m = (l+r)>>1; return max(get(ll, rr, l, m, now<<1), get(ll, rr, m+1, r, now<<1|1)); } int main(){ int i,j,k,l,a,b,c,d; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lld",&num[i]); build(); scanf("%d",&q); for(i=1;i<=q;i++){ scanf("%d%d",&L[i],&R[i]); Q[L[i]].pb(i); } for(i = n; i > 0; i--){ while(!sta.empty()){ a = sta.back(); add(2*a-i, n, num[sta.back()]+num[i]); if(num[sta.back()] < num[i]) sta.pop_back(); else break; } sta.pb(i); for(int it : Q[i]){ ANS[it] = get(i, R[it]); } } for(i=1;i<=q;i++) printf("%d\n",ANS[i]); return 0; } /* 5 5 4 4 5 4 1 1 5 15 12 96 100 61 54 66 37 34 58 21 21 1 13 50 81 12 1 15 3 12 11 14 1 13 5 9 4 6 6 14 2 5 4 15 1 7 1 10 8 13 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12152 KB | Output is correct |
2 | Correct | 12 ms | 12152 KB | Output is correct |
3 | Correct | 13 ms | 12280 KB | Output is correct |
4 | Correct | 13 ms | 12152 KB | Output is correct |
5 | Correct | 15 ms | 12152 KB | Output is correct |
6 | Correct | 17 ms | 12152 KB | Output is correct |
7 | Correct | 13 ms | 12152 KB | Output is correct |
8 | Correct | 14 ms | 12152 KB | Output is correct |
9 | Correct | 6 ms | 12124 KB | Output is correct |
10 | Correct | 17 ms | 12152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12152 KB | Output is correct |
2 | Correct | 12 ms | 12152 KB | Output is correct |
3 | Correct | 13 ms | 12280 KB | Output is correct |
4 | Correct | 13 ms | 12152 KB | Output is correct |
5 | Correct | 15 ms | 12152 KB | Output is correct |
6 | Correct | 17 ms | 12152 KB | Output is correct |
7 | Correct | 13 ms | 12152 KB | Output is correct |
8 | Correct | 14 ms | 12152 KB | Output is correct |
9 | Correct | 6 ms | 12124 KB | Output is correct |
10 | Correct | 17 ms | 12152 KB | Output is correct |
11 | Correct | 456 ms | 26752 KB | Output is correct |
12 | Correct | 446 ms | 26552 KB | Output is correct |
13 | Correct | 448 ms | 26616 KB | Output is correct |
14 | Correct | 461 ms | 26932 KB | Output is correct |
15 | Correct | 458 ms | 26780 KB | Output is correct |
16 | Correct | 470 ms | 26092 KB | Output is correct |
17 | Correct | 447 ms | 26068 KB | Output is correct |
18 | Correct | 455 ms | 25860 KB | Output is correct |
19 | Correct | 479 ms | 26628 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 206 ms | 26076 KB | Output is correct |
2 | Correct | 127 ms | 26956 KB | Output is correct |
3 | Correct | 126 ms | 26012 KB | Output is correct |
4 | Correct | 204 ms | 26000 KB | Output is correct |
5 | Correct | 207 ms | 25948 KB | Output is correct |
6 | Correct | 171 ms | 26108 KB | Output is correct |
7 | Correct | 194 ms | 25924 KB | Output is correct |
8 | Correct | 196 ms | 26104 KB | Output is correct |
9 | Correct | 201 ms | 25992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12152 KB | Output is correct |
2 | Correct | 12 ms | 12152 KB | Output is correct |
3 | Correct | 13 ms | 12280 KB | Output is correct |
4 | Correct | 13 ms | 12152 KB | Output is correct |
5 | Correct | 15 ms | 12152 KB | Output is correct |
6 | Correct | 17 ms | 12152 KB | Output is correct |
7 | Correct | 13 ms | 12152 KB | Output is correct |
8 | Correct | 14 ms | 12152 KB | Output is correct |
9 | Correct | 6 ms | 12124 KB | Output is correct |
10 | Correct | 17 ms | 12152 KB | Output is correct |
11 | Correct | 456 ms | 26752 KB | Output is correct |
12 | Correct | 446 ms | 26552 KB | Output is correct |
13 | Correct | 448 ms | 26616 KB | Output is correct |
14 | Correct | 461 ms | 26932 KB | Output is correct |
15 | Correct | 458 ms | 26780 KB | Output is correct |
16 | Correct | 470 ms | 26092 KB | Output is correct |
17 | Correct | 447 ms | 26068 KB | Output is correct |
18 | Correct | 455 ms | 25860 KB | Output is correct |
19 | Correct | 479 ms | 26628 KB | Output is correct |
20 | Correct | 206 ms | 26076 KB | Output is correct |
21 | Correct | 127 ms | 26956 KB | Output is correct |
22 | Correct | 126 ms | 26012 KB | Output is correct |
23 | Correct | 204 ms | 26000 KB | Output is correct |
24 | Correct | 207 ms | 25948 KB | Output is correct |
25 | Correct | 171 ms | 26108 KB | Output is correct |
26 | Correct | 194 ms | 25924 KB | Output is correct |
27 | Correct | 196 ms | 26104 KB | Output is correct |
28 | Correct | 201 ms | 25992 KB | Output is correct |
29 | Correct | 1545 ms | 60512 KB | Output is correct |
30 | Correct | 1335 ms | 62536 KB | Output is correct |
31 | Correct | 1323 ms | 60516 KB | Output is correct |
32 | Correct | 1552 ms | 60396 KB | Output is correct |
33 | Correct | 1557 ms | 60584 KB | Output is correct |
34 | Correct | 1576 ms | 59896 KB | Output is correct |
35 | Correct | 1557 ms | 60152 KB | Output is correct |
36 | Correct | 1532 ms | 59960 KB | Output is correct |
37 | Correct | 1562 ms | 60488 KB | Output is correct |
38 | Correct | 1040 ms | 67188 KB | Output is correct |
39 | Correct | 1026 ms | 67104 KB | Output is correct |
40 | Correct | 974 ms | 65336 KB | Output is correct |
41 | Correct | 1039 ms | 65192 KB | Output is correct |
42 | Correct | 978 ms | 65372 KB | Output is correct |
43 | Correct | 982 ms | 66088 KB | Output is correct |
44 | Correct | 1090 ms | 66456 KB | Output is correct |
45 | Correct | 1092 ms | 66664 KB | Output is correct |
46 | Correct | 1065 ms | 65024 KB | Output is correct |
47 | Correct | 1064 ms | 64804 KB | Output is correct |
48 | Correct | 1063 ms | 64708 KB | Output is correct |
49 | Correct | 1107 ms | 66196 KB | Output is correct |
50 | Correct | 1197 ms | 64376 KB | Output is correct |
51 | Correct | 1208 ms | 64148 KB | Output is correct |
52 | Correct | 1196 ms | 63412 KB | Output is correct |
53 | Correct | 1185 ms | 63292 KB | Output is correct |
54 | Correct | 1195 ms | 63460 KB | Output is correct |
55 | Correct | 1197 ms | 64020 KB | Output is correct |