| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1068676 |
2024-08-21T11:18:33 Z |
n1k |
Radio Towers (IOI22_towers) |
C++17 |
|
884 ms |
13012 KB |
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct V{
int lb=0, rb=0;
ll mx = 0;
V *l=nullptr, *r=nullptr;
V(){};
V(int lb_, int rb_){lb=lb_, rb=rb_;};
void ext(){
if(lb!=rb and not l){
int mb=(lb+rb)/2;
l=new V(lb, mb);
r=new V(mb+1, rb);
}
}
void upd(int id, ll x){
if(lb==rb and lb==id){
mx = x;
}
ext();
if(l){
if(id<=l->rb){
l->upd(id, x);
}else{
r->upd(id, x);
}
mx = max(l->mx, r->mx);
}
}
ll qry(int lo, int hi){
if(lo<=lb and rb<=hi){
return mx;
}
if(hi<lb or rb<lo) return 0;
ext();
return max(l->qry(lo, hi), r->qry(lo, hi));
}
};
vector<int> sl, sr;
vector<ll> order;
vector<int> get(vector<int> h){
vector<int> sl(h.size());
vector<pair<int, int>> st;
for(int i=0; i<h.size(); i++){
while(st.size() and st.back().first>h[i]){
st.pop_back();
}
if(st.empty()){
sl[i]=i;
}else{
sl[i]=st.back().second;
}
st.push_back({h[i], i});
}
return sl;
}
void init(int N, std::vector<int> H) {
order.clear();
sl = get(H);
reverse(H.begin(), H.end());
sr = get(H);
reverse(H.begin(), H.end());
reverse(sr.begin(), sr.end());
V seg(0, N-1);
for(int i=0; i<sr.size(); i++){
seg.upd(i, H[i]);
sr[i]=N-sr[i]-1;
}
for(int i=0; i<N; i++){
ll minh = int(1e9) + 5;
if(sl[i]!=i){
minh = min(minh, seg.qry(sl[i]+1, i));
}
if(sr[i]!=i){
minh = min(minh, seg.qry(i, sr[i]-1));
}
order.push_back(minh - H[i]);
}
sort(order.begin(), order.end());
for(auto x:order) cerr<<x<<" ";cerr<<endl;
}
int max_towers(int L, int R, int D) {
return order.end() - lower_bound(order.begin(), order.end(), D);
}
Compilation message
towers.cpp: In function 'std::vector<int> get(std::vector<int>)':
towers.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0; i<h.size(); i++){
| ~^~~~~~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0; i<sr.size(); i++){
| ~^~~~~~~~~~
towers.cpp:90:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
90 | for(auto x:order) cerr<<x<<" ";cerr<<endl;
| ^~~
towers.cpp:90:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
90 | for(auto x:order) cerr<<x<<" ";cerr<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
423 ms |
8028 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
751 ms |
13012 KB |
1st lines differ - on the 1st token, expected: '11903', found: '33010' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
3416 KB |
Output is correct |
| 2 |
Incorrect |
884 ms |
12996 KB |
13344th lines differ - on the 1st token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
423 ms |
8028 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
