#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=2e5+5,oo=INT_MAX;
vector<pair<int,pair<int,int> > > antene(N);
vector<ll> solq(N,-1);
struct segTree{
vector<ll> c,d,lazy;
void init()
{
c.clear();
d.clear();
lazy.clear();
c.resize(4*N,-oo);
d.resize(4*N,-1);
lazy.resize(4*N,oo);
}
void prop(int i)
{
if(lazy[i]==oo)
return;
d[2*i]=max(d[2*i],c[2*i]-lazy[i]);
d[2*i+1]=max(d[2*i+1],c[2*i+1]-lazy[i]);
lazy[2*i]=min(lazy[2*i],lazy[i]);
lazy[2*i+1]=min(lazy[2*i+1],lazy[i]);
lazy[i]=oo;
}
void upd(int i)
{
d[i]=max(d[2*i],d[2*i+1]);
c[i]=max(c[2*i],c[2*i+1]);
}
void update(int qs,int qe,ll h,int l=0,int r=N-1,int i=1)
{
/*if(i==1)
{
printf("UPDATE %i %i %lld\n",qs,qe,h);
}*/
if(qs>qe)
return;
if(qs>r||qe<l)
return;
if(qs<=l&&qe>=r)
{
d[i]=max(d[i],c[i]-h);
lazy[i]=min(h,lazy[i]);
return;
}
prop(i);
int m=(l+r)>>1;
update(qs,qe,h,l,m,2*i);
update(qs,qe,h,m+1,r,2*i+1);
upd(i);
}
ll get(int qs,int qe,int l=0,int r=N-1,int i=1)
{
/*if(i==1)
{
printf("GET: %i %i\n",qs,qe);
}*/
if(qs>r||qe<l)
return -1;
if(qs<=l&&qe>=r)
return d[i];
prop(i);
int m=(l+r)>>1;
return max(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1));
}
void set(int pos,ll val,int l=0,int r=N-1,int i=1)
{
/*if(i==1)
{
printf("SET: %i %lld\n",pos,val);
}*/
if(l>pos||r<pos)
return;
if(l==pos&&r==pos)
{
c[i]=val;
return;
}
prop(i);
int m=(l+r)>>1;
set(pos,val,l,m,2*i);
set(pos,val,m+1,r,2*i+1);
upd(i);
}
}st;
int main()
{
int n;
scanf("%i",&n);
vector<pair<int,pair<int,int> > > events1,events2;
for(int i=0;i<n;i++)
{
int h,a,b;
scanf("%i %i %i",&h,&a,&b);
antene[i].f=h;
antene[i].s.f=a;
antene[i].s.s=b;
events1.pb({i+a,{-2,i}});
events1.pb({i,{-1,i}});
events1.pb({i+b,{N,i}});
events2.pb({i,{N,i}});
events2.pb({i-a,{N+1,i}});
events2.pb({i-b,{-1,i}});
}
int q;
scanf("%i",&q);
for(int i=0;i<q;i++)
{
int l,r;
scanf("%i %i",&l,&r);
l--;r--;
events1.pb({r,{l,i}});
events2.pb({l,{r,i}});
}
sort(all(events1));
sort(all(events2));
reverse(all(events2));
st.init();
for(auto p:events1)
{
if(p.s.f==-2)
{
st.set(p.s.s,antene[p.s.s].f);
continue;
}
if(p.s.f==-1)
{
st.update(max(p.s.s-antene[p.s.s].s.s,0),p.s.s-antene[p.s.s].s.f,antene[p.s.s].f);
continue;
}
if(p.s.f==N)
{
st.set(p.s.s,-oo);
continue;
}
int i=p.s.s;
solq[i]=max(solq[i],st.get(p.s.f,p.f));
}
st.init();
for(auto p:events2)
{
if(p.s.f==N+1)
{
st.set(p.s.s,antene[p.s.s].f);
continue;
}
if(p.s.f==N)
{
st.update(p.s.s+antene[p.s.s].s.f,min(p.s.s+antene[p.s.s].s.s,n-1),antene[p.s.s].f);
continue;
}
if(p.s.f==-1)
{
st.set(p.s.s,-oo);
continue;
}
int i=p.s.s;
solq[i]=max(solq[i],st.get(p.f,p.s.f));
}
for(int i=0;i<q;i++)
printf("%i\n",solq[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:188:30: warning: format '%i' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' [-Wformat=]
printf("%i\n",solq[i]);
^
antennas.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
antennas.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&h,&a,&b);
~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&q);
~~~~~^~~~~~~~~
antennas.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&l,&r);
~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
23040 KB |
Output is correct |
2 |
Correct |
27 ms |
23040 KB |
Output is correct |
3 |
Correct |
30 ms |
23040 KB |
Output is correct |
4 |
Correct |
28 ms |
23168 KB |
Output is correct |
5 |
Correct |
28 ms |
23076 KB |
Output is correct |
6 |
Correct |
27 ms |
23032 KB |
Output is correct |
7 |
Correct |
29 ms |
23136 KB |
Output is correct |
8 |
Correct |
24 ms |
23032 KB |
Output is correct |
9 |
Correct |
24 ms |
23040 KB |
Output is correct |
10 |
Correct |
25 ms |
23140 KB |
Output is correct |
11 |
Correct |
23 ms |
23040 KB |
Output is correct |
12 |
Correct |
26 ms |
23168 KB |
Output is correct |
13 |
Correct |
25 ms |
23040 KB |
Output is correct |
14 |
Correct |
28 ms |
23168 KB |
Output is correct |
15 |
Correct |
29 ms |
23032 KB |
Output is correct |
16 |
Correct |
25 ms |
23136 KB |
Output is correct |
17 |
Correct |
26 ms |
23032 KB |
Output is correct |
18 |
Correct |
31 ms |
23040 KB |
Output is correct |
19 |
Correct |
27 ms |
23120 KB |
Output is correct |
20 |
Correct |
27 ms |
23040 KB |
Output is correct |
21 |
Correct |
25 ms |
23040 KB |
Output is correct |
22 |
Correct |
26 ms |
23168 KB |
Output is correct |
23 |
Correct |
26 ms |
23032 KB |
Output is correct |
24 |
Correct |
25 ms |
23168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
23040 KB |
Output is correct |
2 |
Correct |
27 ms |
23040 KB |
Output is correct |
3 |
Correct |
30 ms |
23040 KB |
Output is correct |
4 |
Correct |
28 ms |
23168 KB |
Output is correct |
5 |
Correct |
28 ms |
23076 KB |
Output is correct |
6 |
Correct |
27 ms |
23032 KB |
Output is correct |
7 |
Correct |
29 ms |
23136 KB |
Output is correct |
8 |
Correct |
24 ms |
23032 KB |
Output is correct |
9 |
Correct |
24 ms |
23040 KB |
Output is correct |
10 |
Correct |
25 ms |
23140 KB |
Output is correct |
11 |
Correct |
23 ms |
23040 KB |
Output is correct |
12 |
Correct |
26 ms |
23168 KB |
Output is correct |
13 |
Correct |
25 ms |
23040 KB |
Output is correct |
14 |
Correct |
28 ms |
23168 KB |
Output is correct |
15 |
Correct |
29 ms |
23032 KB |
Output is correct |
16 |
Correct |
25 ms |
23136 KB |
Output is correct |
17 |
Correct |
26 ms |
23032 KB |
Output is correct |
18 |
Correct |
31 ms |
23040 KB |
Output is correct |
19 |
Correct |
27 ms |
23120 KB |
Output is correct |
20 |
Correct |
27 ms |
23040 KB |
Output is correct |
21 |
Correct |
25 ms |
23040 KB |
Output is correct |
22 |
Correct |
26 ms |
23168 KB |
Output is correct |
23 |
Correct |
26 ms |
23032 KB |
Output is correct |
24 |
Correct |
25 ms |
23168 KB |
Output is correct |
25 |
Correct |
194 ms |
29324 KB |
Output is correct |
26 |
Correct |
52 ms |
24116 KB |
Output is correct |
27 |
Correct |
256 ms |
31816 KB |
Output is correct |
28 |
Correct |
238 ms |
31768 KB |
Output is correct |
29 |
Correct |
176 ms |
29208 KB |
Output is correct |
30 |
Correct |
183 ms |
29080 KB |
Output is correct |
31 |
Correct |
232 ms |
31040 KB |
Output is correct |
32 |
Correct |
259 ms |
32024 KB |
Output is correct |
33 |
Correct |
256 ms |
31132 KB |
Output is correct |
34 |
Correct |
139 ms |
27428 KB |
Output is correct |
35 |
Correct |
229 ms |
31736 KB |
Output is correct |
36 |
Correct |
261 ms |
31784 KB |
Output is correct |
37 |
Correct |
137 ms |
27684 KB |
Output is correct |
38 |
Correct |
253 ms |
30844 KB |
Output is correct |
39 |
Correct |
56 ms |
24704 KB |
Output is correct |
40 |
Correct |
242 ms |
30764 KB |
Output is correct |
41 |
Correct |
207 ms |
28836 KB |
Output is correct |
42 |
Correct |
301 ms |
30872 KB |
Output is correct |
43 |
Correct |
99 ms |
25892 KB |
Output is correct |
44 |
Correct |
252 ms |
30744 KB |
Output is correct |
45 |
Correct |
76 ms |
24748 KB |
Output is correct |
46 |
Correct |
235 ms |
30744 KB |
Output is correct |
47 |
Correct |
83 ms |
25388 KB |
Output is correct |
48 |
Correct |
256 ms |
30892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
888 ms |
40248 KB |
Output is correct |
2 |
Correct |
1046 ms |
42088 KB |
Output is correct |
3 |
Correct |
641 ms |
36488 KB |
Output is correct |
4 |
Correct |
1102 ms |
42088 KB |
Output is correct |
5 |
Correct |
416 ms |
31908 KB |
Output is correct |
6 |
Correct |
1045 ms |
41916 KB |
Output is correct |
7 |
Correct |
780 ms |
39472 KB |
Output is correct |
8 |
Correct |
1070 ms |
42028 KB |
Output is correct |
9 |
Correct |
119 ms |
26276 KB |
Output is correct |
10 |
Correct |
922 ms |
42040 KB |
Output is correct |
11 |
Correct |
557 ms |
34952 KB |
Output is correct |
12 |
Correct |
917 ms |
42056 KB |
Output is correct |
13 |
Correct |
536 ms |
42088 KB |
Output is correct |
14 |
Correct |
526 ms |
41928 KB |
Output is correct |
15 |
Correct |
498 ms |
41972 KB |
Output is correct |
16 |
Correct |
521 ms |
41836 KB |
Output is correct |
17 |
Correct |
580 ms |
41960 KB |
Output is correct |
18 |
Correct |
515 ms |
41956 KB |
Output is correct |
19 |
Correct |
528 ms |
41844 KB |
Output is correct |
20 |
Correct |
538 ms |
41948 KB |
Output is correct |
21 |
Correct |
558 ms |
41932 KB |
Output is correct |
22 |
Correct |
516 ms |
41800 KB |
Output is correct |
23 |
Correct |
526 ms |
41960 KB |
Output is correct |
24 |
Correct |
519 ms |
41828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
23040 KB |
Output is correct |
2 |
Correct |
27 ms |
23040 KB |
Output is correct |
3 |
Correct |
30 ms |
23040 KB |
Output is correct |
4 |
Correct |
28 ms |
23168 KB |
Output is correct |
5 |
Correct |
28 ms |
23076 KB |
Output is correct |
6 |
Correct |
27 ms |
23032 KB |
Output is correct |
7 |
Correct |
29 ms |
23136 KB |
Output is correct |
8 |
Correct |
24 ms |
23032 KB |
Output is correct |
9 |
Correct |
24 ms |
23040 KB |
Output is correct |
10 |
Correct |
25 ms |
23140 KB |
Output is correct |
11 |
Correct |
23 ms |
23040 KB |
Output is correct |
12 |
Correct |
26 ms |
23168 KB |
Output is correct |
13 |
Correct |
25 ms |
23040 KB |
Output is correct |
14 |
Correct |
28 ms |
23168 KB |
Output is correct |
15 |
Correct |
29 ms |
23032 KB |
Output is correct |
16 |
Correct |
25 ms |
23136 KB |
Output is correct |
17 |
Correct |
26 ms |
23032 KB |
Output is correct |
18 |
Correct |
31 ms |
23040 KB |
Output is correct |
19 |
Correct |
27 ms |
23120 KB |
Output is correct |
20 |
Correct |
27 ms |
23040 KB |
Output is correct |
21 |
Correct |
25 ms |
23040 KB |
Output is correct |
22 |
Correct |
26 ms |
23168 KB |
Output is correct |
23 |
Correct |
26 ms |
23032 KB |
Output is correct |
24 |
Correct |
25 ms |
23168 KB |
Output is correct |
25 |
Correct |
194 ms |
29324 KB |
Output is correct |
26 |
Correct |
52 ms |
24116 KB |
Output is correct |
27 |
Correct |
256 ms |
31816 KB |
Output is correct |
28 |
Correct |
238 ms |
31768 KB |
Output is correct |
29 |
Correct |
176 ms |
29208 KB |
Output is correct |
30 |
Correct |
183 ms |
29080 KB |
Output is correct |
31 |
Correct |
232 ms |
31040 KB |
Output is correct |
32 |
Correct |
259 ms |
32024 KB |
Output is correct |
33 |
Correct |
256 ms |
31132 KB |
Output is correct |
34 |
Correct |
139 ms |
27428 KB |
Output is correct |
35 |
Correct |
229 ms |
31736 KB |
Output is correct |
36 |
Correct |
261 ms |
31784 KB |
Output is correct |
37 |
Correct |
137 ms |
27684 KB |
Output is correct |
38 |
Correct |
253 ms |
30844 KB |
Output is correct |
39 |
Correct |
56 ms |
24704 KB |
Output is correct |
40 |
Correct |
242 ms |
30764 KB |
Output is correct |
41 |
Correct |
207 ms |
28836 KB |
Output is correct |
42 |
Correct |
301 ms |
30872 KB |
Output is correct |
43 |
Correct |
99 ms |
25892 KB |
Output is correct |
44 |
Correct |
252 ms |
30744 KB |
Output is correct |
45 |
Correct |
76 ms |
24748 KB |
Output is correct |
46 |
Correct |
235 ms |
30744 KB |
Output is correct |
47 |
Correct |
83 ms |
25388 KB |
Output is correct |
48 |
Correct |
256 ms |
30892 KB |
Output is correct |
49 |
Correct |
888 ms |
40248 KB |
Output is correct |
50 |
Correct |
1046 ms |
42088 KB |
Output is correct |
51 |
Correct |
641 ms |
36488 KB |
Output is correct |
52 |
Correct |
1102 ms |
42088 KB |
Output is correct |
53 |
Correct |
416 ms |
31908 KB |
Output is correct |
54 |
Correct |
1045 ms |
41916 KB |
Output is correct |
55 |
Correct |
780 ms |
39472 KB |
Output is correct |
56 |
Correct |
1070 ms |
42028 KB |
Output is correct |
57 |
Correct |
119 ms |
26276 KB |
Output is correct |
58 |
Correct |
922 ms |
42040 KB |
Output is correct |
59 |
Correct |
557 ms |
34952 KB |
Output is correct |
60 |
Correct |
917 ms |
42056 KB |
Output is correct |
61 |
Correct |
536 ms |
42088 KB |
Output is correct |
62 |
Correct |
526 ms |
41928 KB |
Output is correct |
63 |
Correct |
498 ms |
41972 KB |
Output is correct |
64 |
Correct |
521 ms |
41836 KB |
Output is correct |
65 |
Correct |
580 ms |
41960 KB |
Output is correct |
66 |
Correct |
515 ms |
41956 KB |
Output is correct |
67 |
Correct |
528 ms |
41844 KB |
Output is correct |
68 |
Correct |
538 ms |
41948 KB |
Output is correct |
69 |
Correct |
558 ms |
41932 KB |
Output is correct |
70 |
Correct |
516 ms |
41800 KB |
Output is correct |
71 |
Correct |
526 ms |
41960 KB |
Output is correct |
72 |
Correct |
519 ms |
41828 KB |
Output is correct |
73 |
Correct |
1222 ms |
46980 KB |
Output is correct |
74 |
Correct |
1142 ms |
42684 KB |
Output is correct |
75 |
Correct |
1281 ms |
45600 KB |
Output is correct |
76 |
Correct |
1457 ms |
51336 KB |
Output is correct |
77 |
Correct |
688 ms |
38408 KB |
Output is correct |
78 |
Correct |
1319 ms |
48148 KB |
Output is correct |
79 |
Correct |
1281 ms |
48732 KB |
Output is correct |
80 |
Correct |
1511 ms |
51260 KB |
Output is correct |
81 |
Correct |
446 ms |
34836 KB |
Output is correct |
82 |
Correct |
1215 ms |
46432 KB |
Output is correct |
83 |
Correct |
891 ms |
44132 KB |
Output is correct |
84 |
Correct |
1490 ms |
51428 KB |
Output is correct |
85 |
Correct |
795 ms |
46524 KB |
Output is correct |
86 |
Correct |
936 ms |
50024 KB |
Output is correct |
87 |
Correct |
556 ms |
42980 KB |
Output is correct |
88 |
Correct |
936 ms |
50124 KB |
Output is correct |
89 |
Correct |
880 ms |
47800 KB |
Output is correct |
90 |
Correct |
879 ms |
50036 KB |
Output is correct |
91 |
Correct |
673 ms |
44652 KB |
Output is correct |
92 |
Correct |
928 ms |
50056 KB |
Output is correct |
93 |
Correct |
648 ms |
43172 KB |
Output is correct |
94 |
Correct |
883 ms |
50020 KB |
Output is correct |
95 |
Correct |
711 ms |
44024 KB |
Output is correct |
96 |
Correct |
894 ms |
49988 KB |
Output is correct |