제출 #1212621

#제출 시각아이디문제언어결과실행 시간메모리
1212621nerrrminRadio Towers (IOI22_towers)C++20
23 / 100
4043 ms8064 KiB
#include "towers.h" #define pb push_back #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int n; int a[maxn], t[maxn * 4]; map < int, int > mp; void build(int i, int l, int r) { if(l == r) { t[i] = a[l]; return; } int mid = (l + r)/2; build(2*i, l, mid); build(2*i+1, mid+1, r); t[i] = max(t[2*i], t[2*i+1]); } int ql, qr; int query(int i, int l, int r) { if(qr < l || ql > r)return 0; if(ql <= l && r <= qr)return t[i]; int mid = (l + r)/2; return (query(2*i, l, mid), query(2*i+1, mid+1, r)); } void init(int N, std::vector<int> H) { n = N; for (int i = 0; i < n; ++ i) { a[i] = H[i]; mp[a[i]] = i; } } int last[maxn], nxt[maxn]; int active[maxn]; int max_towers(int L, int R, int D) { for (int i = L; i <= R; ++ i) active[i] = 0; vector < pair < int, int > > g; for (int i = L; i <= R; ++ i) { g.pb(make_pair(a[i], i)); } sort(g.begin(), g.end()); int cnt = 0; for (auto &[val, i]: g) { /// cout << val << " " << i << endl; int found = 0, no = 0; for (int j = i-1; j >= L; -- j) { if(a[j] >= val + D) { found = 1; break; } if(active[j]) { no = 1; break; } } ///cout << "found1 " << found << endl; if(no)continue; found = 0; for (int j = i+1; j <= R; ++ j) { if(a[j] >= val + D) { found = 1; break; } if(active[j]) { no = 1; break; } } if(no)continue; /// cout <<"found2 " << found << endl; active[i] = 1; cnt ++; } return cnt; }
#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...