Submission #774632

#TimeUsernameProblemLanguageResultExecution timeMemory
774632Magikarp4000Radio Towers (IOI22_towers)C++17
23 / 100
4098 ms4972 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; const int MAXN = 1e5+5; int n,l,r,d; int h[MAXN], le[MAXN], ri[MAXN]; set<int> s; bool check(int start) { FORR(i,start-1,-1) { if (s.count(i)) return 0; if (h[i] >= h[start]+d) return 1; } return 1; } bool check1(int start) { FOR(i,start+1,n) { if (s.count(i)) return 0; if (h[i] >= h[start]+d) return 1; } return 1; } void init(int N, std::vector<int> H) { n = N; FOR(i,0,n) h[i] = H[i]; } int max_towers(int L, int R, int D) { s.clear(); l = L, r = R, d = D; vector<PII> v; FOR(i,l,r+1) v.PB({h[i],i}); sort(ALL(v)); int vn = v.size(); PQ<PII> pq; FOR(i,l,r+1) { while (!pq.empty() && -pq.top().F <= h[i]-d) { ri[pq.top().S] = i; pq.pop(); } pq.push({-h[i],i}); } while (!pq.empty()) { ri[pq.top().S] = n; pq.pop(); } FORR(i,r,l-1) { while (!pq.empty() && -pq.top().F <= h[i]-d) { le[pq.top().S] = i; pq.pop(); } pq.push({-h[i],i}); } while (!pq.empty()) { le[pq.top().S] = -1; pq.pop(); } // FOR(i,0,n) cout << le[i] << " "; // cout << ln; // FOR(i,0,n) cout << ri[i] << " "; // cout << ln; s.insert(-INF); s.insert(INF); FOR(i,0,vn) { int idx = v[i].S; auto it = s.lower_bound(idx); auto it1 = it; it1--; if (le[idx] > (*it1) && ri[idx] < (*it)) s.insert(idx); } return s.size()-2; }
#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...