// Author: Kajetan Ramsza
#include "bits/stdc++.h"
#include "towers.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#ifdef DEBUG
auto &operator<<(auto &os, const pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto &operator<<(auto &os, const auto &v) {
os << "{";
for(auto it=begin(v);it!=end(v);it++) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x)
#else
#define dbg(...)
#endif
int count_larger(const vi &vec, int x) {
dbg(vec);
int b = 0, e = sz(vec);
while(b < e) {
int mid = (b+e) / 2;
if(vec[mid] < x) b = mid + 1;
else e = mid;
}
return sz(vec) - b;
}
struct SegTree {
int n;
vector<vi> tree;
SegTree() {}
SegTree(vi vals) {
n = 1;
while(n < sz(vals))
n *= 2;
tree.assign(2*n, {});
rep(i,0,n)
if(i < sz(vals))
tree[n+i] = {vals[i]};
else
tree[n+i] = {-1};
dbg(tree);
for(int i=n-1;i>0;i--)
merge(all(tree[2*i]), all(tree[2*i+1]), back_inserter(tree[i]));
dbg(tree);
}
int query(int l, int r, int x) {
int res = 0;
for(l+=n, r+=n; l<r; l/=2, r/=2) {
if(l&1) res += count_larger(tree[l++], x);
if(r&1) res += count_larger(tree[--r], x);
}
return res;
}
};
const int inf = 2e9 + 7;
int n;
vi h;
vi sel;
vi tim;
SegTree *tree;
void init(int N, vi H) {
n = N;
h = H;
sel.assign(n, 0);
int prev = -1;
bool small = false;
rep(i,0,n) {
if(small) {
if(prev != -1 && h[i] < h[prev]) {
sel[prev] = false;
sel[i] = true;
prev = i;
}
else {
prev = i;
sel[i] = true;
small = false;
}
} else {
if(prev != -1 && h[i] > h[prev]) {
sel[prev] = false;
sel[i] = true;
prev = i;
}
else {
prev = i;
sel[i] = true;
small = true;
}
}
}
tim.assign(n, -1);
prev = -1;
int parity = 1;
int prev_tim = -1;
rep(i,0,n) {
if(!sel[i])
continue;
if(prev != -1) {
if(parity)
tim[i] = min(prev_tim, (int)abs(h[prev] - h[i]));
else
prev_tim = (int)abs(h[prev] - h[i]);
} else if(parity)
tim[i] = inf;
prev = i;
parity ^= 1;
}
tree = new SegTree(tim);
}
int max_towers(int L, int R, int D) {
int num = tree->query(0, n, D);
if(num == 0) return 1;
dbg(D, num);
return num;
// return (num + 1) / 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
12500 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 |
0 ms |
596 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 |
0 ms |
596 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 |
541 ms |
24364 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 |
Incorrect |
209 ms |
6232 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7097' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
596 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 |
323 ms |
12500 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
