#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10],dp[N];
pair<int,int>num[N],pw[N],sorted[N];
vi g[N];
void upd(int ind,int x){
for(ind+=SS;ind>0;ind>>=1) seg[ind]=max(seg[ind],x);
}
int Query(int a,int b){
int res=0;
for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
if(!(a&1)) res=max(res,seg[a+1]);
if(b&1) res=max(res,seg[b-1]);
}
return res;
}
void cnt(int l,int r,int d){
for(int i=1;i<=SS*2;i++) seg[i]=0;
for(int i=l;i<=r;i++){
sorted[i-l+1]={t[i],i};
sorted[r-l+1+i-l+1]={t[i]+d,i+r};
}
sort(sorted+1,sorted+1+(r-l+1)*2);
int wsk=0;
for(int i=1;i<=(r-l+1)*2;i++){
if(i==1 or sorted[i].fi!=sorted[i-1].fi) wsk++;
if(sorted[i].se>r) num[sorted[i].se-r].se=wsk;
else num[sorted[i].se].fi=wsk;
}
for(int i=l;i<=r;i++){
pw[i].fi=Query(num[i].se,wsk);
upd(num[i].fi,i);
}
for(int i=1;i<=SS*2;i++) seg[i]=0;
for(int i=r;i>=l;i--){
pw[i].se=Query(num[i].se,wsk);
if(pw[i].se!=0) pw[i].se=r-pw[i].se+1;
upd(num[i].fi,r-i+1);
}
for(int i=1;i<=SS*2;i++) seg[i]=0;
}
void init(int n,vi a){
for(int i=0;i<n;i++) t[i+1]=a[i];
}
int max_towers(int l,int r,int d){
l++,r++;
cnt(l,r,d);
int res=0;
for(int i=l;i<=r;i++){
if(pw[i].fi!=0) dp[i]=Query(l,pw[i].fi-1);
dp[i]++;
res=max(res,dp[i]);
if(pw[i].se!=0) g[pw[i].se].push_back(i);
for(auto u:g[i]) upd(u,dp[u]);
}
return res;
}
/*int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int n;
cin>>n;
vi xd;
for(int i=1;i<=n;i++){
int a;
cin>>a;
xd.push_back(a);
}
init(n,xd);
int q;
cin>>q;
while(q--){
int l,r,d;
cin>>l>>r>>d;
cout<<max_towers(l,r,d)<<"\n";
}
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4073 ms |
40220 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
27856 KB |
Output is correct |
2 |
Correct |
15 ms |
27984 KB |
Output is correct |
3 |
Correct |
16 ms |
27856 KB |
Output is correct |
4 |
Correct |
15 ms |
27856 KB |
Output is correct |
5 |
Correct |
16 ms |
27856 KB |
Output is correct |
6 |
Correct |
15 ms |
27856 KB |
Output is correct |
7 |
Correct |
18 ms |
27880 KB |
Output is correct |
8 |
Correct |
17 ms |
27868 KB |
Output is correct |
9 |
Correct |
16 ms |
27864 KB |
Output is correct |
10 |
Correct |
16 ms |
27840 KB |
Output is correct |
11 |
Correct |
16 ms |
27884 KB |
Output is correct |
12 |
Correct |
16 ms |
27856 KB |
Output is correct |
13 |
Correct |
15 ms |
27984 KB |
Output is correct |
14 |
Correct |
15 ms |
27856 KB |
Output is correct |
15 |
Correct |
18 ms |
27956 KB |
Output is correct |
16 |
Correct |
15 ms |
27984 KB |
Output is correct |
17 |
Correct |
15 ms |
27856 KB |
Output is correct |
18 |
Correct |
16 ms |
27856 KB |
Output is correct |
19 |
Correct |
16 ms |
27856 KB |
Output is correct |
20 |
Correct |
20 ms |
27984 KB |
Output is correct |
21 |
Correct |
16 ms |
27952 KB |
Output is correct |
22 |
Correct |
17 ms |
28020 KB |
Output is correct |
23 |
Correct |
17 ms |
27984 KB |
Output is correct |
24 |
Correct |
15 ms |
27948 KB |
Output is correct |
25 |
Correct |
15 ms |
27872 KB |
Output is correct |
26 |
Correct |
16 ms |
27980 KB |
Output is correct |
27 |
Correct |
15 ms |
27984 KB |
Output is correct |
28 |
Correct |
15 ms |
28012 KB |
Output is correct |
29 |
Correct |
16 ms |
28024 KB |
Output is correct |
30 |
Correct |
16 ms |
27984 KB |
Output is correct |
31 |
Correct |
15 ms |
27916 KB |
Output is correct |
32 |
Correct |
16 ms |
27984 KB |
Output is correct |
33 |
Correct |
15 ms |
28004 KB |
Output is correct |
34 |
Correct |
16 ms |
27904 KB |
Output is correct |
35 |
Correct |
19 ms |
27984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
27856 KB |
Output is correct |
2 |
Correct |
15 ms |
27984 KB |
Output is correct |
3 |
Correct |
16 ms |
27856 KB |
Output is correct |
4 |
Correct |
15 ms |
27856 KB |
Output is correct |
5 |
Correct |
16 ms |
27856 KB |
Output is correct |
6 |
Correct |
15 ms |
27856 KB |
Output is correct |
7 |
Correct |
18 ms |
27880 KB |
Output is correct |
8 |
Correct |
17 ms |
27868 KB |
Output is correct |
9 |
Correct |
16 ms |
27864 KB |
Output is correct |
10 |
Correct |
16 ms |
27840 KB |
Output is correct |
11 |
Correct |
16 ms |
27884 KB |
Output is correct |
12 |
Correct |
16 ms |
27856 KB |
Output is correct |
13 |
Correct |
15 ms |
27984 KB |
Output is correct |
14 |
Correct |
15 ms |
27856 KB |
Output is correct |
15 |
Correct |
18 ms |
27956 KB |
Output is correct |
16 |
Correct |
15 ms |
27984 KB |
Output is correct |
17 |
Correct |
15 ms |
27856 KB |
Output is correct |
18 |
Correct |
16 ms |
27856 KB |
Output is correct |
19 |
Correct |
16 ms |
27856 KB |
Output is correct |
20 |
Correct |
20 ms |
27984 KB |
Output is correct |
21 |
Correct |
16 ms |
27952 KB |
Output is correct |
22 |
Correct |
17 ms |
28020 KB |
Output is correct |
23 |
Correct |
17 ms |
27984 KB |
Output is correct |
24 |
Correct |
15 ms |
27948 KB |
Output is correct |
25 |
Correct |
15 ms |
27872 KB |
Output is correct |
26 |
Correct |
16 ms |
27980 KB |
Output is correct |
27 |
Correct |
15 ms |
27984 KB |
Output is correct |
28 |
Correct |
15 ms |
28012 KB |
Output is correct |
29 |
Correct |
16 ms |
28024 KB |
Output is correct |
30 |
Correct |
16 ms |
27984 KB |
Output is correct |
31 |
Correct |
15 ms |
27916 KB |
Output is correct |
32 |
Correct |
16 ms |
27984 KB |
Output is correct |
33 |
Correct |
15 ms |
28004 KB |
Output is correct |
34 |
Correct |
16 ms |
27904 KB |
Output is correct |
35 |
Correct |
19 ms |
27984 KB |
Output is correct |
36 |
Correct |
32 ms |
29264 KB |
Output is correct |
37 |
Correct |
42 ms |
29988 KB |
Output is correct |
38 |
Correct |
34 ms |
29276 KB |
Output is correct |
39 |
Correct |
40 ms |
29804 KB |
Output is correct |
40 |
Correct |
43 ms |
29272 KB |
Output is correct |
41 |
Correct |
74 ms |
32352 KB |
Output is correct |
42 |
Correct |
26 ms |
28816 KB |
Output is correct |
43 |
Correct |
49 ms |
30920 KB |
Output is correct |
44 |
Correct |
28 ms |
29164 KB |
Output is correct |
45 |
Correct |
29 ms |
28776 KB |
Output is correct |
46 |
Correct |
26 ms |
28632 KB |
Output is correct |
47 |
Correct |
47 ms |
30488 KB |
Output is correct |
48 |
Correct |
37 ms |
29780 KB |
Output is correct |
49 |
Correct |
30 ms |
29020 KB |
Output is correct |
50 |
Correct |
41 ms |
29388 KB |
Output is correct |
51 |
Correct |
51 ms |
31320 KB |
Output is correct |
52 |
Correct |
94 ms |
33836 KB |
Output is correct |
53 |
Correct |
85 ms |
33764 KB |
Output is correct |
54 |
Correct |
84 ms |
33848 KB |
Output is correct |
55 |
Correct |
68 ms |
32244 KB |
Output is correct |
56 |
Correct |
74 ms |
35232 KB |
Output is correct |
57 |
Correct |
77 ms |
32488 KB |
Output is correct |
58 |
Correct |
75 ms |
32936 KB |
Output is correct |
59 |
Correct |
91 ms |
33208 KB |
Output is correct |
60 |
Correct |
86 ms |
33824 KB |
Output is correct |
61 |
Correct |
96 ms |
33620 KB |
Output is correct |
62 |
Correct |
81 ms |
33312 KB |
Output is correct |
63 |
Correct |
78 ms |
33628 KB |
Output is correct |
64 |
Correct |
55 ms |
32896 KB |
Output is correct |
65 |
Correct |
65 ms |
32104 KB |
Output is correct |
66 |
Correct |
57 ms |
33084 KB |
Output is correct |
67 |
Correct |
57 ms |
32204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4049 ms |
55100 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4073 ms |
40140 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
27856 KB |
Output is correct |
2 |
Correct |
15 ms |
27984 KB |
Output is correct |
3 |
Correct |
16 ms |
27856 KB |
Output is correct |
4 |
Correct |
15 ms |
27856 KB |
Output is correct |
5 |
Correct |
16 ms |
27856 KB |
Output is correct |
6 |
Correct |
15 ms |
27856 KB |
Output is correct |
7 |
Correct |
18 ms |
27880 KB |
Output is correct |
8 |
Correct |
17 ms |
27868 KB |
Output is correct |
9 |
Correct |
16 ms |
27864 KB |
Output is correct |
10 |
Correct |
16 ms |
27840 KB |
Output is correct |
11 |
Correct |
16 ms |
27884 KB |
Output is correct |
12 |
Correct |
16 ms |
27856 KB |
Output is correct |
13 |
Correct |
15 ms |
27984 KB |
Output is correct |
14 |
Correct |
15 ms |
27856 KB |
Output is correct |
15 |
Correct |
18 ms |
27956 KB |
Output is correct |
16 |
Correct |
15 ms |
27984 KB |
Output is correct |
17 |
Correct |
15 ms |
27856 KB |
Output is correct |
18 |
Correct |
16 ms |
27856 KB |
Output is correct |
19 |
Correct |
16 ms |
27856 KB |
Output is correct |
20 |
Correct |
20 ms |
27984 KB |
Output is correct |
21 |
Correct |
16 ms |
27952 KB |
Output is correct |
22 |
Correct |
17 ms |
28020 KB |
Output is correct |
23 |
Correct |
17 ms |
27984 KB |
Output is correct |
24 |
Correct |
15 ms |
27948 KB |
Output is correct |
25 |
Correct |
15 ms |
27872 KB |
Output is correct |
26 |
Correct |
16 ms |
27980 KB |
Output is correct |
27 |
Correct |
15 ms |
27984 KB |
Output is correct |
28 |
Correct |
15 ms |
28012 KB |
Output is correct |
29 |
Correct |
16 ms |
28024 KB |
Output is correct |
30 |
Correct |
16 ms |
27984 KB |
Output is correct |
31 |
Correct |
15 ms |
27916 KB |
Output is correct |
32 |
Correct |
16 ms |
27984 KB |
Output is correct |
33 |
Correct |
15 ms |
28004 KB |
Output is correct |
34 |
Correct |
16 ms |
27904 KB |
Output is correct |
35 |
Correct |
19 ms |
27984 KB |
Output is correct |
36 |
Correct |
32 ms |
29264 KB |
Output is correct |
37 |
Correct |
42 ms |
29988 KB |
Output is correct |
38 |
Correct |
34 ms |
29276 KB |
Output is correct |
39 |
Correct |
40 ms |
29804 KB |
Output is correct |
40 |
Correct |
43 ms |
29272 KB |
Output is correct |
41 |
Correct |
74 ms |
32352 KB |
Output is correct |
42 |
Correct |
26 ms |
28816 KB |
Output is correct |
43 |
Correct |
49 ms |
30920 KB |
Output is correct |
44 |
Correct |
28 ms |
29164 KB |
Output is correct |
45 |
Correct |
29 ms |
28776 KB |
Output is correct |
46 |
Correct |
26 ms |
28632 KB |
Output is correct |
47 |
Correct |
47 ms |
30488 KB |
Output is correct |
48 |
Correct |
37 ms |
29780 KB |
Output is correct |
49 |
Correct |
30 ms |
29020 KB |
Output is correct |
50 |
Correct |
41 ms |
29388 KB |
Output is correct |
51 |
Correct |
51 ms |
31320 KB |
Output is correct |
52 |
Correct |
94 ms |
33836 KB |
Output is correct |
53 |
Correct |
85 ms |
33764 KB |
Output is correct |
54 |
Correct |
84 ms |
33848 KB |
Output is correct |
55 |
Correct |
68 ms |
32244 KB |
Output is correct |
56 |
Correct |
74 ms |
35232 KB |
Output is correct |
57 |
Correct |
77 ms |
32488 KB |
Output is correct |
58 |
Correct |
75 ms |
32936 KB |
Output is correct |
59 |
Correct |
91 ms |
33208 KB |
Output is correct |
60 |
Correct |
86 ms |
33824 KB |
Output is correct |
61 |
Correct |
96 ms |
33620 KB |
Output is correct |
62 |
Correct |
81 ms |
33312 KB |
Output is correct |
63 |
Correct |
78 ms |
33628 KB |
Output is correct |
64 |
Correct |
55 ms |
32896 KB |
Output is correct |
65 |
Correct |
65 ms |
32104 KB |
Output is correct |
66 |
Correct |
57 ms |
33084 KB |
Output is correct |
67 |
Correct |
57 ms |
32204 KB |
Output is correct |
68 |
Execution timed out |
4049 ms |
55100 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4073 ms |
40220 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |