#include "towers.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef pair<int,int> pii;
int n;
int v[100005];
int rmq[22][100005];
int loga[100005];
void init(int N, std::vector<int> H) {
n=N;
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
for(int j=0;j<=20;j++)
if((1<<j)<=i)
loga[i]=j;
}
for(int i=n;i>=1;i--)
{
rmq[0][i]=v[i];
for(int j=1;j<=20;j++)
{
rmq[j][i]=rmq[j-1][i];
int poz=i+(1<<(j-1));
if(poz<=n)
rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
}
}
}
int dp[100005];
int arb[4*100005];
vector<int> add[100005];
int getmax(int l,int r)
{
int lg=loga[r-l+1];
return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
int getR(int poz,int delta)
{
int st=poz+2;
int dr=n;
int ans=1e9;
while(st<=dr)
{
int mij=(st+dr)/2;
if(getmax(poz+1,mij-1)-delta>=v[poz])
{
ans=mij;
dr=mij-1;
}
else
st=mij+1;
}
return ans;
}
int getL(int poz,int delta)
{
bool ok=0;
if(poz==4)
ok=1;
int st=1;
int dr=poz-2;
int ans=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(getmax(mij+1,poz-1)-delta>=v[poz])
{
ans=mij;
st=mij+1;
}
else
dr=mij-1;
}
return ans;
}
void update(int nod,int st,int dr,int poz,int val)
{
if(st==dr)
{
arb[nod]=val;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
update(nod*2,st,mij,poz,val);
else
update(nod*2+1,mij+1,dr,poz,val);
arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
if(st>=a&&dr<=b)
return arb[nod];
int mij=(st+dr)/2;
int rez=0;
if(a<=mij)
rez=max(rez,query(nod*2,st,mij,a,b));
if(b>mij)
rez=max(rez,query(nod*2+1,mij+1,dr,a,b));
return rez;
}
int max_towers(int L, int R, int D)
{
L++;
R++;
for(int i=1;i<=4*n;i++)
arb[i]=0;
for(int i=1;i<=n;i++)
add[i].clear();
int ans=1;
for(int i=L;i<=R;i++)
{
for(int j:add[i])
update(1,1,n,j,dp[j]);
dp[i]=1;
int r=getR(i,D);
int l=getL(i,D);
if(l>=L)
dp[i]=1+query(1,1,n,L,l);
ans=max(ans,dp[i]);
if(r<=R)
add[r].push_back(i);
}
for(int i=R;i>=L;i--)
if(v[i]<=v[i-1]||i==L)
return dp[i];
}
Compilation message
towers.cpp: In function 'int getL(int, int)':
towers.cpp:59:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
59 | bool ok=0;
| ^~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
129 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4073 ms |
11404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2816 KB |
Output is correct |
2 |
Correct |
2 ms |
2896 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2896 KB |
1st lines differ - on the 1st token, expected: '91', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2816 KB |
Output is correct |
2 |
Correct |
2 ms |
2896 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2896 KB |
1st lines differ - on the 1st token, expected: '91', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4088 ms |
15700 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4094 ms |
5872 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2816 KB |
Output is correct |
2 |
Correct |
2 ms |
2896 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2896 KB |
1st lines differ - on the 1st token, expected: '91', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4073 ms |
11404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |