| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1020315 |
2024-07-11T22:13:38 Z |
kym |
Radio Towers (IOI22_towers) |
C++17 |
|
4000 ms |
5072 KB |
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int>A;
int n;
struct node {
int tree[4*MAXN];
void build(int node, int s, int e){
tree[node]=0;
if(s!=e){
int m=(s+e)/2;
build(node<<1,s,m);
build(node<<1|1,m+1,e);
}
}
void update(int node, int s, int e, int x, int nval){
if(s==e){
tree[node]=nval;
return;
}
int m=(s+e)/2;
if(x<=m)update(node<<1,s,m,x,nval);
else update(node<<1|1,m+1,e,x,nval);
tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
int query(int node, int s, int e, int x, int y){
if(s==x&&e==y)return tree[node];
int m=(s+e)/2;
if(y<=m)return query(node<<1,s,m,x,y);
else if(x>m)return query(node<<1|1,m+1,e,x,y);
else return max(query(node<<1,s,m,x,m),query(node<<1|1,m+1,e,m+1,y));
}
int walk(int node, int s, int e, int tar){
if(s==e)return s;
int m=(s+e)/2;
if(tree[node<<1|1]>=tar)return walk(node<<1|1,m+1,e,tar);
else return walk(node<<1,s,m,tar);
}
}seg,sa;
int ls[MAXN];
void init(int N, std::vector<int> H) {
n=N;
A=H;
}
typedef pair<int,int>pi;
int max_towers(int L, int R, int D) {
sa.build(1,0,n);
seg.build(1,0,n);
int dp[n+5];memset(dp,0,sizeof dp);
for(int i=0;i<n;i++)dp[i]=1;
int ans=1;
priority_queue<pi,vector<pi>,greater<pi>>pq;
for(int i=L;i<=R;i++){
int lf=sa.walk(1,0,n,A[i]+D);
if(L<=lf-1){
int mx=seg.query(1,0,n,L,lf-1);
dp[i]=max(dp[i],mx+1);
ans=max(ans,dp[i]);
}
while(pq.size() && pq.top().first <= A[i]-D){
pi cur=pq.top();pq.pop();
//cerr<<cur.second<<" "<<dp[cur.second]<<"\n";
seg.update(1,0,n,cur.second,dp[cur.second]);
}
sa.update(1,0,n,i,A[i]);
pq.push({A[i],i});
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4013 ms |
3412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
1 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
1 ms |
344 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
1 ms |
344 KB |
Output is correct |
| 35 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
1 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
1 ms |
344 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
1 ms |
344 KB |
Output is correct |
| 35 |
Correct |
1 ms |
344 KB |
Output is correct |
| 36 |
Correct |
13 ms |
2136 KB |
Output is correct |
| 37 |
Correct |
15 ms |
4036 KB |
Output is correct |
| 38 |
Correct |
13 ms |
3772 KB |
Output is correct |
| 39 |
Correct |
13 ms |
4048 KB |
Output is correct |
| 40 |
Correct |
13 ms |
3536 KB |
Output is correct |
| 41 |
Correct |
36 ms |
4492 KB |
Output is correct |
| 42 |
Correct |
10 ms |
3536 KB |
Output is correct |
| 43 |
Correct |
18 ms |
4028 KB |
Output is correct |
| 44 |
Correct |
11 ms |
3792 KB |
Output is correct |
| 45 |
Correct |
10 ms |
3520 KB |
Output is correct |
| 46 |
Correct |
10 ms |
3536 KB |
Output is correct |
| 47 |
Correct |
23 ms |
3680 KB |
Output is correct |
| 48 |
Correct |
15 ms |
3676 KB |
Output is correct |
| 49 |
Correct |
12 ms |
3536 KB |
Output is correct |
| 50 |
Correct |
14 ms |
4048 KB |
Output is correct |
| 51 |
Correct |
23 ms |
3516 KB |
Output is correct |
| 52 |
Correct |
34 ms |
3536 KB |
Output is correct |
| 53 |
Correct |
34 ms |
3604 KB |
Output is correct |
| 54 |
Correct |
34 ms |
3536 KB |
Output is correct |
| 55 |
Correct |
27 ms |
5072 KB |
Output is correct |
| 56 |
Correct |
26 ms |
3536 KB |
Output is correct |
| 57 |
Correct |
35 ms |
4544 KB |
Output is correct |
| 58 |
Correct |
33 ms |
4296 KB |
Output is correct |
| 59 |
Correct |
36 ms |
4048 KB |
Output is correct |
| 60 |
Correct |
40 ms |
3536 KB |
Output is correct |
| 61 |
Correct |
35 ms |
4040 KB |
Output is correct |
| 62 |
Correct |
40 ms |
4548 KB |
Output is correct |
| 63 |
Correct |
35 ms |
4052 KB |
Output is correct |
| 64 |
Correct |
32 ms |
4560 KB |
Output is correct |
| 65 |
Correct |
30 ms |
5072 KB |
Output is correct |
| 66 |
Correct |
28 ms |
4048 KB |
Output is correct |
| 67 |
Correct |
22 ms |
5072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4025 ms |
3540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4006 ms |
1836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
0 ms |
596 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
344 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
344 KB |
Output is correct |
| 19 |
Correct |
0 ms |
344 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
344 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
344 KB |
Output is correct |
| 24 |
Correct |
1 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
1 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
1 ms |
344 KB |
Output is correct |
| 32 |
Correct |
1 ms |
344 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
1 ms |
344 KB |
Output is correct |
| 35 |
Correct |
1 ms |
344 KB |
Output is correct |
| 36 |
Correct |
13 ms |
2136 KB |
Output is correct |
| 37 |
Correct |
15 ms |
4036 KB |
Output is correct |
| 38 |
Correct |
13 ms |
3772 KB |
Output is correct |
| 39 |
Correct |
13 ms |
4048 KB |
Output is correct |
| 40 |
Correct |
13 ms |
3536 KB |
Output is correct |
| 41 |
Correct |
36 ms |
4492 KB |
Output is correct |
| 42 |
Correct |
10 ms |
3536 KB |
Output is correct |
| 43 |
Correct |
18 ms |
4028 KB |
Output is correct |
| 44 |
Correct |
11 ms |
3792 KB |
Output is correct |
| 45 |
Correct |
10 ms |
3520 KB |
Output is correct |
| 46 |
Correct |
10 ms |
3536 KB |
Output is correct |
| 47 |
Correct |
23 ms |
3680 KB |
Output is correct |
| 48 |
Correct |
15 ms |
3676 KB |
Output is correct |
| 49 |
Correct |
12 ms |
3536 KB |
Output is correct |
| 50 |
Correct |
14 ms |
4048 KB |
Output is correct |
| 51 |
Correct |
23 ms |
3516 KB |
Output is correct |
| 52 |
Correct |
34 ms |
3536 KB |
Output is correct |
| 53 |
Correct |
34 ms |
3604 KB |
Output is correct |
| 54 |
Correct |
34 ms |
3536 KB |
Output is correct |
| 55 |
Correct |
27 ms |
5072 KB |
Output is correct |
| 56 |
Correct |
26 ms |
3536 KB |
Output is correct |
| 57 |
Correct |
35 ms |
4544 KB |
Output is correct |
| 58 |
Correct |
33 ms |
4296 KB |
Output is correct |
| 59 |
Correct |
36 ms |
4048 KB |
Output is correct |
| 60 |
Correct |
40 ms |
3536 KB |
Output is correct |
| 61 |
Correct |
35 ms |
4040 KB |
Output is correct |
| 62 |
Correct |
40 ms |
4548 KB |
Output is correct |
| 63 |
Correct |
35 ms |
4052 KB |
Output is correct |
| 64 |
Correct |
32 ms |
4560 KB |
Output is correct |
| 65 |
Correct |
30 ms |
5072 KB |
Output is correct |
| 66 |
Correct |
28 ms |
4048 KB |
Output is correct |
| 67 |
Correct |
22 ms |
5072 KB |
Output is correct |
| 68 |
Execution timed out |
4025 ms |
3540 KB |
Time limit exceeded |
| 69 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4013 ms |
3412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
