Submission #1054161

#TimeUsernameProblemLanguageResultExecution timeMemory
1054161GrayRadio Towers (IOI22_towers)C++17
14 / 100
705 ms24280 KiB
#include "towers.h" #include <algorithm> #include <vector> #include <iostream> #define ll int #define ff first #define ss second #define ln "\n" using namespace std; struct SegTree{ #define node vector<ll> vector<node> t; ll sz, rsz; void init(ll N){ sz=N*4; rsz=N; t.resize(sz); } void clear(){ t.clear(); sz=rsz=0; } void merge(node &p, node &l, node &r){ ll p1=0, p2=0; while (p1<(ll)l.size() or p2<(ll)r.size()){ if (p2==(ll)r.size() or (p1<(ll)l.size() and l[p1]<r[p2])){ p.push_back(l[p1++]); }else{ p.push_back(r[p2++]); } } } void build(ll tl, ll tr, ll v, vector<ll> &a){ if (tl==tr){ ll dif=0; if (tl-1>=0 and tl+1<(ll)a.size()){ dif=max(dif, min(a[tl]-a[tl-1], a[tl]-a[tl+1])); } t[v].push_back(dif); }else{ ll tm = (tl+tr)/2; build(tl, tm, v*2, a); build(tm+1, tr, v*2+1, a); merge(t[v], t[v*2], t[v*2+1]); } } void build(vector<ll> &a){ build(0, rsz-1, 1, a); } void query(ll tl, ll tr, ll v, ll l, ll r, ll D, ll &wr){ if (tl==l and tr==r){ wr+=(ll)t[v].size()-(lower_bound(t[v].begin(), t[v].end(), D)-t[v].begin()); }else if (l>r) return; else{ ll tm = (tl+tr)/2; query(tl, tm, v*2, l, min(r, tm), D, wr); query(tm+1, tr, v*2+1, max(l, tm+1), r, D, wr); } } ll query(ll l, ll r, ll D){ ll res=0; query(0, rsz-1, 1, l, r, D, res); return res; } }; vector<ll> fa; SegTree tr; ll fn; void init(int N, std::vector<int> H) { fa=H; fn=N; tr.clear(); tr.init(N); tr.build(fa); } // smallt -> // bigt -> int max_towers(int L, int R, int D) { return tr.query(L+1, R-1, D)+1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...