# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
250863 |
2020-07-19T10:16:16 Z |
combi1k1 |
Fire (JOI20_ho_t5) |
C++14 |
|
368 ms |
54552 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define X first
#define Y second
const int N = 4e5 + 5;
typedef pair<ll,ll> pll;
struct BIT {
pll T[N];
int upd(int p,pll d) {
for(p += N / 2 ; p < N ; p += p & -p)
T[p].X += d.X,
T[p].Y += d.Y;
return 1;
}
ll get(int p,int x) {
ll s = 0;
ll c = 0;
for(p += N / 2 + 1 ; p > 0 ; p -= p & -p)
s += T[p].X,
c += T[p].Y;
return s * x - c;
}
} pref;
BIT suff;
int a[N];
int l[N];
int r[N];
vector<tuple<int,int,int> > Upd[N];
vector<tuple<int,int,int> > Que[N];
void Add(int l,int r,int v) {
if (l > r) return;
int k = r - l + 1;
Upd[0].pb(l,r, v);
Upd[k].pb(l,r,-v);
}
ll ask(int T,int r) {
ll ans = 0;
ans += suff.get(r,r); r -= T;
ans += pref.get(r,r);
return ans;
}
ll ans[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int q; cin >> q;
for(int i = 1 ; i <= n ; ++i)
cin >> a[i];
stack<int> st;
for(int i = 1 ; i <= n ; ++i) {
while (st.size() && a[st.top()] <= a[i])
st.pop();
if (st.size()) l[i] = st.top() + 1;
else l[i] = -n;
st.push(i);
}
while (st.size()) st.pop();
for(int i = n ; i >= 1 ; --i) {
while (st.size() && a[st.top()] < a[i])
st.pop();
if (st.size()) r[i] = st.top() - 1;
else r[i] = n;
st.push(i);
}
for(int i = 1 ; i <= n ; ++i) {
Add(l[i] ,r[i] , a[i]);
Add(l[i] ,i - 1,-a[i]);
Add(i + 1,r[i] ,-a[i]);
}
for(int i = 0 ; i < q ; ++i) {
int t; cin >> t;
int l; cin >> l;
int r; cin >> r;
Que[t].pb(l,r,i);
}
for(int t = 0 ; t <= n ; ++t) {
for(auto it : Upd[t]) {
int l, r, v;
tie(l, r, v) = it; ++r;
pref.upd(l,pll( v, 1ll * v * (l - 1)));
suff.upd(r,pll(-v,-1ll * v * (r - 1)));
}
for(auto it : Que[t]) {
int l, r, i;
tie(l, r, i) = it;
ans[i] += ask(t,r);
ans[i] -= ask(t,l - 1);
}
}
for(int i = 0 ; i < q ; ++i)
cout << ans[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19200 KB |
Output is correct |
2 |
Correct |
14 ms |
19200 KB |
Output is correct |
3 |
Correct |
12 ms |
19200 KB |
Output is correct |
4 |
Correct |
12 ms |
19200 KB |
Output is correct |
5 |
Correct |
12 ms |
19200 KB |
Output is correct |
6 |
Correct |
12 ms |
19200 KB |
Output is correct |
7 |
Correct |
12 ms |
19200 KB |
Output is correct |
8 |
Correct |
12 ms |
19308 KB |
Output is correct |
9 |
Correct |
12 ms |
19200 KB |
Output is correct |
10 |
Correct |
12 ms |
19200 KB |
Output is correct |
11 |
Correct |
12 ms |
19200 KB |
Output is correct |
12 |
Correct |
12 ms |
19200 KB |
Output is correct |
13 |
Correct |
12 ms |
19200 KB |
Output is correct |
14 |
Correct |
14 ms |
19200 KB |
Output is correct |
15 |
Correct |
14 ms |
19200 KB |
Output is correct |
16 |
Correct |
14 ms |
19200 KB |
Output is correct |
17 |
Correct |
15 ms |
19200 KB |
Output is correct |
18 |
Correct |
12 ms |
19200 KB |
Output is correct |
19 |
Correct |
12 ms |
19200 KB |
Output is correct |
20 |
Correct |
14 ms |
19200 KB |
Output is correct |
21 |
Correct |
14 ms |
19200 KB |
Output is correct |
22 |
Correct |
14 ms |
19200 KB |
Output is correct |
23 |
Correct |
14 ms |
19200 KB |
Output is correct |
24 |
Correct |
14 ms |
19200 KB |
Output is correct |
25 |
Correct |
14 ms |
19200 KB |
Output is correct |
26 |
Correct |
14 ms |
19200 KB |
Output is correct |
27 |
Correct |
15 ms |
19200 KB |
Output is correct |
28 |
Correct |
14 ms |
19200 KB |
Output is correct |
29 |
Correct |
15 ms |
19200 KB |
Output is correct |
30 |
Correct |
14 ms |
19200 KB |
Output is correct |
31 |
Correct |
12 ms |
19200 KB |
Output is correct |
32 |
Correct |
14 ms |
19200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19200 KB |
Output is correct |
2 |
Correct |
216 ms |
50968 KB |
Output is correct |
3 |
Correct |
228 ms |
52760 KB |
Output is correct |
4 |
Correct |
224 ms |
53144 KB |
Output is correct |
5 |
Correct |
204 ms |
54040 KB |
Output is correct |
6 |
Correct |
209 ms |
52760 KB |
Output is correct |
7 |
Correct |
203 ms |
53272 KB |
Output is correct |
8 |
Correct |
206 ms |
54552 KB |
Output is correct |
9 |
Correct |
210 ms |
53668 KB |
Output is correct |
10 |
Correct |
202 ms |
52760 KB |
Output is correct |
11 |
Correct |
209 ms |
54040 KB |
Output is correct |
12 |
Correct |
200 ms |
52892 KB |
Output is correct |
13 |
Correct |
208 ms |
53912 KB |
Output is correct |
14 |
Correct |
202 ms |
54040 KB |
Output is correct |
15 |
Correct |
228 ms |
54040 KB |
Output is correct |
16 |
Correct |
209 ms |
53144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19200 KB |
Output is correct |
2 |
Correct |
268 ms |
49304 KB |
Output is correct |
3 |
Correct |
257 ms |
50460 KB |
Output is correct |
4 |
Correct |
263 ms |
52376 KB |
Output is correct |
5 |
Correct |
268 ms |
50840 KB |
Output is correct |
6 |
Correct |
262 ms |
51096 KB |
Output is correct |
7 |
Correct |
330 ms |
51104 KB |
Output is correct |
8 |
Correct |
337 ms |
50840 KB |
Output is correct |
9 |
Correct |
304 ms |
50844 KB |
Output is correct |
10 |
Correct |
243 ms |
50456 KB |
Output is correct |
11 |
Correct |
310 ms |
52376 KB |
Output is correct |
12 |
Correct |
249 ms |
51736 KB |
Output is correct |
13 |
Correct |
266 ms |
51480 KB |
Output is correct |
14 |
Correct |
263 ms |
50712 KB |
Output is correct |
15 |
Correct |
257 ms |
51480 KB |
Output is correct |
16 |
Correct |
251 ms |
51096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
48408 KB |
Output is correct |
2 |
Correct |
234 ms |
49048 KB |
Output is correct |
3 |
Correct |
248 ms |
49688 KB |
Output is correct |
4 |
Correct |
300 ms |
49304 KB |
Output is correct |
5 |
Correct |
233 ms |
49048 KB |
Output is correct |
6 |
Correct |
308 ms |
49304 KB |
Output is correct |
7 |
Correct |
244 ms |
49552 KB |
Output is correct |
8 |
Correct |
259 ms |
49632 KB |
Output is correct |
9 |
Correct |
307 ms |
49176 KB |
Output is correct |
10 |
Correct |
238 ms |
49560 KB |
Output is correct |
11 |
Correct |
233 ms |
49436 KB |
Output is correct |
12 |
Correct |
278 ms |
49588 KB |
Output is correct |
13 |
Correct |
303 ms |
49308 KB |
Output is correct |
14 |
Correct |
260 ms |
49304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
19200 KB |
Output is correct |
2 |
Correct |
14 ms |
19200 KB |
Output is correct |
3 |
Correct |
12 ms |
19200 KB |
Output is correct |
4 |
Correct |
12 ms |
19200 KB |
Output is correct |
5 |
Correct |
12 ms |
19200 KB |
Output is correct |
6 |
Correct |
12 ms |
19200 KB |
Output is correct |
7 |
Correct |
12 ms |
19200 KB |
Output is correct |
8 |
Correct |
12 ms |
19308 KB |
Output is correct |
9 |
Correct |
12 ms |
19200 KB |
Output is correct |
10 |
Correct |
12 ms |
19200 KB |
Output is correct |
11 |
Correct |
12 ms |
19200 KB |
Output is correct |
12 |
Correct |
12 ms |
19200 KB |
Output is correct |
13 |
Correct |
12 ms |
19200 KB |
Output is correct |
14 |
Correct |
14 ms |
19200 KB |
Output is correct |
15 |
Correct |
14 ms |
19200 KB |
Output is correct |
16 |
Correct |
14 ms |
19200 KB |
Output is correct |
17 |
Correct |
15 ms |
19200 KB |
Output is correct |
18 |
Correct |
12 ms |
19200 KB |
Output is correct |
19 |
Correct |
12 ms |
19200 KB |
Output is correct |
20 |
Correct |
14 ms |
19200 KB |
Output is correct |
21 |
Correct |
14 ms |
19200 KB |
Output is correct |
22 |
Correct |
14 ms |
19200 KB |
Output is correct |
23 |
Correct |
14 ms |
19200 KB |
Output is correct |
24 |
Correct |
14 ms |
19200 KB |
Output is correct |
25 |
Correct |
14 ms |
19200 KB |
Output is correct |
26 |
Correct |
14 ms |
19200 KB |
Output is correct |
27 |
Correct |
15 ms |
19200 KB |
Output is correct |
28 |
Correct |
14 ms |
19200 KB |
Output is correct |
29 |
Correct |
15 ms |
19200 KB |
Output is correct |
30 |
Correct |
14 ms |
19200 KB |
Output is correct |
31 |
Correct |
12 ms |
19200 KB |
Output is correct |
32 |
Correct |
14 ms |
19200 KB |
Output is correct |
33 |
Correct |
264 ms |
49944 KB |
Output is correct |
34 |
Correct |
314 ms |
52632 KB |
Output is correct |
35 |
Correct |
362 ms |
52248 KB |
Output is correct |
36 |
Correct |
290 ms |
52060 KB |
Output is correct |
37 |
Correct |
263 ms |
51736 KB |
Output is correct |
38 |
Correct |
368 ms |
52120 KB |
Output is correct |
39 |
Correct |
284 ms |
51960 KB |
Output is correct |
40 |
Correct |
276 ms |
51608 KB |
Output is correct |
41 |
Correct |
284 ms |
52888 KB |
Output is correct |
42 |
Correct |
281 ms |
52032 KB |
Output is correct |
43 |
Correct |
256 ms |
52376 KB |
Output is correct |
44 |
Correct |
226 ms |
52632 KB |
Output is correct |
45 |
Correct |
255 ms |
51352 KB |
Output is correct |
46 |
Correct |
261 ms |
52508 KB |
Output is correct |
47 |
Correct |
231 ms |
51096 KB |
Output is correct |
48 |
Correct |
220 ms |
51096 KB |
Output is correct |
49 |
Correct |
231 ms |
51608 KB |
Output is correct |
50 |
Correct |
231 ms |
52760 KB |
Output is correct |
51 |
Correct |
239 ms |
52888 KB |
Output is correct |
52 |
Correct |
225 ms |
51740 KB |
Output is correct |
53 |
Correct |
218 ms |
51740 KB |
Output is correct |
54 |
Correct |
227 ms |
51096 KB |
Output is correct |
55 |
Correct |
222 ms |
51352 KB |
Output is correct |
56 |
Correct |
258 ms |
51608 KB |
Output is correct |
57 |
Correct |
219 ms |
51164 KB |
Output is correct |
58 |
Correct |
262 ms |
52632 KB |
Output is correct |
59 |
Correct |
216 ms |
50968 KB |
Output is correct |
60 |
Correct |
228 ms |
52760 KB |
Output is correct |
61 |
Correct |
224 ms |
53144 KB |
Output is correct |
62 |
Correct |
204 ms |
54040 KB |
Output is correct |
63 |
Correct |
209 ms |
52760 KB |
Output is correct |
64 |
Correct |
203 ms |
53272 KB |
Output is correct |
65 |
Correct |
206 ms |
54552 KB |
Output is correct |
66 |
Correct |
210 ms |
53668 KB |
Output is correct |
67 |
Correct |
202 ms |
52760 KB |
Output is correct |
68 |
Correct |
209 ms |
54040 KB |
Output is correct |
69 |
Correct |
200 ms |
52892 KB |
Output is correct |
70 |
Correct |
208 ms |
53912 KB |
Output is correct |
71 |
Correct |
202 ms |
54040 KB |
Output is correct |
72 |
Correct |
228 ms |
54040 KB |
Output is correct |
73 |
Correct |
209 ms |
53144 KB |
Output is correct |
74 |
Correct |
268 ms |
49304 KB |
Output is correct |
75 |
Correct |
257 ms |
50460 KB |
Output is correct |
76 |
Correct |
263 ms |
52376 KB |
Output is correct |
77 |
Correct |
268 ms |
50840 KB |
Output is correct |
78 |
Correct |
262 ms |
51096 KB |
Output is correct |
79 |
Correct |
330 ms |
51104 KB |
Output is correct |
80 |
Correct |
337 ms |
50840 KB |
Output is correct |
81 |
Correct |
304 ms |
50844 KB |
Output is correct |
82 |
Correct |
243 ms |
50456 KB |
Output is correct |
83 |
Correct |
310 ms |
52376 KB |
Output is correct |
84 |
Correct |
249 ms |
51736 KB |
Output is correct |
85 |
Correct |
266 ms |
51480 KB |
Output is correct |
86 |
Correct |
263 ms |
50712 KB |
Output is correct |
87 |
Correct |
257 ms |
51480 KB |
Output is correct |
88 |
Correct |
251 ms |
51096 KB |
Output is correct |
89 |
Correct |
238 ms |
48408 KB |
Output is correct |
90 |
Correct |
234 ms |
49048 KB |
Output is correct |
91 |
Correct |
248 ms |
49688 KB |
Output is correct |
92 |
Correct |
300 ms |
49304 KB |
Output is correct |
93 |
Correct |
233 ms |
49048 KB |
Output is correct |
94 |
Correct |
308 ms |
49304 KB |
Output is correct |
95 |
Correct |
244 ms |
49552 KB |
Output is correct |
96 |
Correct |
259 ms |
49632 KB |
Output is correct |
97 |
Correct |
307 ms |
49176 KB |
Output is correct |
98 |
Correct |
238 ms |
49560 KB |
Output is correct |
99 |
Correct |
233 ms |
49436 KB |
Output is correct |
100 |
Correct |
278 ms |
49588 KB |
Output is correct |
101 |
Correct |
303 ms |
49308 KB |
Output is correct |
102 |
Correct |
260 ms |
49304 KB |
Output is correct |