#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "test"
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int N = 2e5+2;
const ll mod = 998244353 ;
const ll base = 350;
const ll inf = 1e15;
ll m, n, t, k, a[N], ans, tong, b[N], c[N], res[N], l[N], r[N];
vector<ll> kq, add[N], del[N];
string s;
vector<pll> val, adj[N];
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n&1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
struct BIT
{
ll n;
vector<ll> fe;
BIT(ll _n)
{
n = _n;
fe.resize(n+1, 0);
}
void add(ll id, ll x)
{
for(; id <= n; id += id & -id)fe[id] += x;
}
ll get(ll id)
{
ll total = 0;
for(; id; id -= id & -id)total += fe[id];
return total;
}
};
struct IT
{
ll n;
vector<ll> mx, mn, st, lazy;
IT(ll _n)
{
n = _n;
st.resize(n*4+4, -inf);
mx.resize(n*4+4, -inf);
mn.resize(n*4+4, inf);
}
void down(ll id)
{
if(mx[id] == -inf)return;
mx[id*2] = max(mx[id*2], mx[id]);
mx[id*2+1] = max(mx[id*2+1], mx[id]);
st[id*2] = max(st[id*2], mx[id*2]-mn[id*2]);
st[id*2+1] = max(st[id*2+1], mx[id*2+1]-mn[id*2+1]);
mx[id] = -inf;
}
void update(ll id, ll l, ll r, ll u, ll v, ll x)
{
if(u <= l && r <= v)
{
mx[id] = max(mx[id], x);
st[id] = max(st[id], mx[id]-mn[id]);
return;
}
if(u > r || l > v)return;
ll mid = (l+r)/2;
down(id);
update(id*2, l, mid, u, v, x);
update(id*2+1, mid+1, r, u, v, x);
st[id] = max(st[id*2], st[id*2+1]);
}
void update(ll l, ll r ,ll x)
{
update(1, 1, n, l, r, x);
}
void build(ll id, ll l, ll r, ll pos, ll x)
{
if(l == r)
{
mx[id] = -inf;
mn[id] = x;
return;
}
ll mid = (l+r)/2;
down(id);
if(pos <= mid)build(id*2, l ,mid, pos, x);
else build(id*2+1, mid+1, r, pos, x);
st[id] = max(st[id*2], st[id*2+1]);
mn[id] = min(mn[id*2], mn[id*2+1]);
}
void build(ll pos, ll x)
{
build(1, 1, n, pos, x);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return -inf;
down(id);
ll mid = (l+r)/2;
return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
ll get(ll l, ll r)
{
return get(1, 1, n, l, r);
}
};
void cal()
{
IT it(n);
for(int i = n; i > 0; i --)
{
for(ll j: add[i])it.build(j, a[j]);
for(ll j: del[i])it.build(j, inf);
if(i-b[i] > 0)add[i-b[i]].pb(i);
if(i-c[i]-1 > 0)del[i-c[i]-1].pb(i);
if(i+b[i] <= n)it.update(i+b[i], min(n, i+c[i]), a[i]);
for(pll j: adj[i])res[j.fi] = max(res[j.fi], it.get(1, j.se));
}
}
void sol()
{
cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i] >> c[i];
cin >> m;
for(int i = 1; i <= m; i ++)
{
cin >> l[i] >> r[i];
adj[l[i]].pb({i, r[i]});
res[i] = -1;
}
cal();
for(int i = 1; i <= n; i ++)
{
adj[i].clear();
add[i].clear();
del[i].clear();
}
for(int i = 1; i <= m; i ++)
{
l[i] = n-l[i]+1;
r[i] = n-r[i]+1;
swap(l[i], r[i]);
adj[l[i]].pb({i, r[i]});
}
reverse(a+1, a+1+n);
reverse(b+1, b+1+n);
reverse(c+1, c+1+n);
cal();
for(int i = 1; i <= m; i ++)
cout << res[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
8 ms |
14424 KB |
Output is correct |
4 |
Correct |
8 ms |
14416 KB |
Output is correct |
5 |
Correct |
8 ms |
14416 KB |
Output is correct |
6 |
Correct |
10 ms |
14544 KB |
Output is correct |
7 |
Correct |
8 ms |
14436 KB |
Output is correct |
8 |
Correct |
9 ms |
14416 KB |
Output is correct |
9 |
Correct |
8 ms |
14504 KB |
Output is correct |
10 |
Correct |
8 ms |
14416 KB |
Output is correct |
11 |
Correct |
8 ms |
14416 KB |
Output is correct |
12 |
Correct |
10 ms |
14524 KB |
Output is correct |
13 |
Correct |
8 ms |
14416 KB |
Output is correct |
14 |
Correct |
9 ms |
14472 KB |
Output is correct |
15 |
Correct |
9 ms |
14416 KB |
Output is correct |
16 |
Correct |
8 ms |
14416 KB |
Output is correct |
17 |
Correct |
9 ms |
14424 KB |
Output is correct |
18 |
Correct |
8 ms |
14428 KB |
Output is correct |
19 |
Correct |
7 ms |
14416 KB |
Output is correct |
20 |
Correct |
7 ms |
14416 KB |
Output is correct |
21 |
Correct |
8 ms |
14416 KB |
Output is correct |
22 |
Correct |
8 ms |
14448 KB |
Output is correct |
23 |
Correct |
8 ms |
14416 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
8 ms |
14424 KB |
Output is correct |
4 |
Correct |
8 ms |
14416 KB |
Output is correct |
5 |
Correct |
8 ms |
14416 KB |
Output is correct |
6 |
Correct |
10 ms |
14544 KB |
Output is correct |
7 |
Correct |
8 ms |
14436 KB |
Output is correct |
8 |
Correct |
9 ms |
14416 KB |
Output is correct |
9 |
Correct |
8 ms |
14504 KB |
Output is correct |
10 |
Correct |
8 ms |
14416 KB |
Output is correct |
11 |
Correct |
8 ms |
14416 KB |
Output is correct |
12 |
Correct |
10 ms |
14524 KB |
Output is correct |
13 |
Correct |
8 ms |
14416 KB |
Output is correct |
14 |
Correct |
9 ms |
14472 KB |
Output is correct |
15 |
Correct |
9 ms |
14416 KB |
Output is correct |
16 |
Correct |
8 ms |
14416 KB |
Output is correct |
17 |
Correct |
9 ms |
14424 KB |
Output is correct |
18 |
Correct |
8 ms |
14428 KB |
Output is correct |
19 |
Correct |
7 ms |
14416 KB |
Output is correct |
20 |
Correct |
7 ms |
14416 KB |
Output is correct |
21 |
Correct |
8 ms |
14416 KB |
Output is correct |
22 |
Correct |
8 ms |
14448 KB |
Output is correct |
23 |
Correct |
8 ms |
14416 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
25 |
Correct |
79 ms |
25736 KB |
Output is correct |
26 |
Correct |
18 ms |
15748 KB |
Output is correct |
27 |
Correct |
112 ms |
29844 KB |
Output is correct |
28 |
Correct |
119 ms |
29800 KB |
Output is correct |
29 |
Correct |
87 ms |
26016 KB |
Output is correct |
30 |
Correct |
77 ms |
25052 KB |
Output is correct |
31 |
Correct |
84 ms |
28744 KB |
Output is correct |
32 |
Correct |
118 ms |
29868 KB |
Output is correct |
33 |
Correct |
98 ms |
29564 KB |
Output is correct |
34 |
Correct |
56 ms |
21968 KB |
Output is correct |
35 |
Correct |
116 ms |
30432 KB |
Output is correct |
36 |
Correct |
109 ms |
29756 KB |
Output is correct |
37 |
Correct |
67 ms |
22856 KB |
Output is correct |
38 |
Correct |
126 ms |
28668 KB |
Output is correct |
39 |
Correct |
25 ms |
16720 KB |
Output is correct |
40 |
Correct |
104 ms |
28708 KB |
Output is correct |
41 |
Correct |
82 ms |
25564 KB |
Output is correct |
42 |
Correct |
110 ms |
28632 KB |
Output is correct |
43 |
Correct |
42 ms |
19516 KB |
Output is correct |
44 |
Correct |
112 ms |
28748 KB |
Output is correct |
45 |
Correct |
26 ms |
17092 KB |
Output is correct |
46 |
Correct |
116 ms |
28768 KB |
Output is correct |
47 |
Correct |
51 ms |
18212 KB |
Output is correct |
48 |
Correct |
103 ms |
28780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
40696 KB |
Output is correct |
2 |
Correct |
429 ms |
43760 KB |
Output is correct |
3 |
Correct |
287 ms |
34856 KB |
Output is correct |
4 |
Correct |
422 ms |
48200 KB |
Output is correct |
5 |
Correct |
170 ms |
29928 KB |
Output is correct |
6 |
Correct |
486 ms |
48292 KB |
Output is correct |
7 |
Correct |
378 ms |
43668 KB |
Output is correct |
8 |
Correct |
432 ms |
48212 KB |
Output is correct |
9 |
Correct |
51 ms |
19764 KB |
Output is correct |
10 |
Correct |
456 ms |
48200 KB |
Output is correct |
11 |
Correct |
242 ms |
35440 KB |
Output is correct |
12 |
Correct |
405 ms |
48204 KB |
Output is correct |
13 |
Correct |
236 ms |
47668 KB |
Output is correct |
14 |
Correct |
235 ms |
47220 KB |
Output is correct |
15 |
Correct |
222 ms |
46200 KB |
Output is correct |
16 |
Correct |
231 ms |
46128 KB |
Output is correct |
17 |
Correct |
254 ms |
48132 KB |
Output is correct |
18 |
Correct |
235 ms |
46596 KB |
Output is correct |
19 |
Correct |
253 ms |
47212 KB |
Output is correct |
20 |
Correct |
227 ms |
47564 KB |
Output is correct |
21 |
Correct |
207 ms |
47732 KB |
Output is correct |
22 |
Correct |
239 ms |
46956 KB |
Output is correct |
23 |
Correct |
230 ms |
47172 KB |
Output is correct |
24 |
Correct |
202 ms |
45676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
8 ms |
14424 KB |
Output is correct |
4 |
Correct |
8 ms |
14416 KB |
Output is correct |
5 |
Correct |
8 ms |
14416 KB |
Output is correct |
6 |
Correct |
10 ms |
14544 KB |
Output is correct |
7 |
Correct |
8 ms |
14436 KB |
Output is correct |
8 |
Correct |
9 ms |
14416 KB |
Output is correct |
9 |
Correct |
8 ms |
14504 KB |
Output is correct |
10 |
Correct |
8 ms |
14416 KB |
Output is correct |
11 |
Correct |
8 ms |
14416 KB |
Output is correct |
12 |
Correct |
10 ms |
14524 KB |
Output is correct |
13 |
Correct |
8 ms |
14416 KB |
Output is correct |
14 |
Correct |
9 ms |
14472 KB |
Output is correct |
15 |
Correct |
9 ms |
14416 KB |
Output is correct |
16 |
Correct |
8 ms |
14416 KB |
Output is correct |
17 |
Correct |
9 ms |
14424 KB |
Output is correct |
18 |
Correct |
8 ms |
14428 KB |
Output is correct |
19 |
Correct |
7 ms |
14416 KB |
Output is correct |
20 |
Correct |
7 ms |
14416 KB |
Output is correct |
21 |
Correct |
8 ms |
14416 KB |
Output is correct |
22 |
Correct |
8 ms |
14448 KB |
Output is correct |
23 |
Correct |
8 ms |
14416 KB |
Output is correct |
24 |
Correct |
8 ms |
14420 KB |
Output is correct |
25 |
Correct |
79 ms |
25736 KB |
Output is correct |
26 |
Correct |
18 ms |
15748 KB |
Output is correct |
27 |
Correct |
112 ms |
29844 KB |
Output is correct |
28 |
Correct |
119 ms |
29800 KB |
Output is correct |
29 |
Correct |
87 ms |
26016 KB |
Output is correct |
30 |
Correct |
77 ms |
25052 KB |
Output is correct |
31 |
Correct |
84 ms |
28744 KB |
Output is correct |
32 |
Correct |
118 ms |
29868 KB |
Output is correct |
33 |
Correct |
98 ms |
29564 KB |
Output is correct |
34 |
Correct |
56 ms |
21968 KB |
Output is correct |
35 |
Correct |
116 ms |
30432 KB |
Output is correct |
36 |
Correct |
109 ms |
29756 KB |
Output is correct |
37 |
Correct |
67 ms |
22856 KB |
Output is correct |
38 |
Correct |
126 ms |
28668 KB |
Output is correct |
39 |
Correct |
25 ms |
16720 KB |
Output is correct |
40 |
Correct |
104 ms |
28708 KB |
Output is correct |
41 |
Correct |
82 ms |
25564 KB |
Output is correct |
42 |
Correct |
110 ms |
28632 KB |
Output is correct |
43 |
Correct |
42 ms |
19516 KB |
Output is correct |
44 |
Correct |
112 ms |
28748 KB |
Output is correct |
45 |
Correct |
26 ms |
17092 KB |
Output is correct |
46 |
Correct |
116 ms |
28768 KB |
Output is correct |
47 |
Correct |
51 ms |
18212 KB |
Output is correct |
48 |
Correct |
103 ms |
28780 KB |
Output is correct |
49 |
Correct |
439 ms |
40696 KB |
Output is correct |
50 |
Correct |
429 ms |
43760 KB |
Output is correct |
51 |
Correct |
287 ms |
34856 KB |
Output is correct |
52 |
Correct |
422 ms |
48200 KB |
Output is correct |
53 |
Correct |
170 ms |
29928 KB |
Output is correct |
54 |
Correct |
486 ms |
48292 KB |
Output is correct |
55 |
Correct |
378 ms |
43668 KB |
Output is correct |
56 |
Correct |
432 ms |
48212 KB |
Output is correct |
57 |
Correct |
51 ms |
19764 KB |
Output is correct |
58 |
Correct |
456 ms |
48200 KB |
Output is correct |
59 |
Correct |
242 ms |
35440 KB |
Output is correct |
60 |
Correct |
405 ms |
48204 KB |
Output is correct |
61 |
Correct |
236 ms |
47668 KB |
Output is correct |
62 |
Correct |
235 ms |
47220 KB |
Output is correct |
63 |
Correct |
222 ms |
46200 KB |
Output is correct |
64 |
Correct |
231 ms |
46128 KB |
Output is correct |
65 |
Correct |
254 ms |
48132 KB |
Output is correct |
66 |
Correct |
235 ms |
46596 KB |
Output is correct |
67 |
Correct |
253 ms |
47212 KB |
Output is correct |
68 |
Correct |
227 ms |
47564 KB |
Output is correct |
69 |
Correct |
207 ms |
47732 KB |
Output is correct |
70 |
Correct |
239 ms |
46956 KB |
Output is correct |
71 |
Correct |
230 ms |
47172 KB |
Output is correct |
72 |
Correct |
202 ms |
45676 KB |
Output is correct |
73 |
Correct |
588 ms |
57992 KB |
Output is correct |
74 |
Correct |
495 ms |
49796 KB |
Output is correct |
75 |
Correct |
579 ms |
55152 KB |
Output is correct |
76 |
Correct |
755 ms |
65704 KB |
Output is correct |
77 |
Correct |
359 ms |
42120 KB |
Output is correct |
78 |
Correct |
628 ms |
60368 KB |
Output is correct |
79 |
Correct |
723 ms |
61128 KB |
Output is correct |
80 |
Correct |
700 ms |
65848 KB |
Output is correct |
81 |
Correct |
196 ms |
33112 KB |
Output is correct |
82 |
Correct |
540 ms |
57232 KB |
Output is correct |
83 |
Correct |
448 ms |
52200 KB |
Output is correct |
84 |
Correct |
648 ms |
65712 KB |
Output is correct |
85 |
Correct |
378 ms |
57488 KB |
Output is correct |
86 |
Correct |
470 ms |
63584 KB |
Output is correct |
87 |
Correct |
265 ms |
48784 KB |
Output is correct |
88 |
Correct |
470 ms |
62308 KB |
Output is correct |
89 |
Correct |
499 ms |
60296 KB |
Output is correct |
90 |
Correct |
544 ms |
62936 KB |
Output is correct |
91 |
Correct |
328 ms |
52960 KB |
Output is correct |
92 |
Correct |
503 ms |
63960 KB |
Output is correct |
93 |
Correct |
289 ms |
50836 KB |
Output is correct |
94 |
Correct |
505 ms |
63540 KB |
Output is correct |
95 |
Correct |
353 ms |
51856 KB |
Output is correct |
96 |
Correct |
476 ms |
62040 KB |
Output is correct |