Submission #1213115

#TimeUsernameProblemLanguageResultExecution timeMemory
1213115nerrrminRadio Towers (IOI22_towers)C++20
37 / 100
4057 ms8196 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; int pref[maxn]; 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; } for (int i = 0; i < n; ++ i) { if(i == 0) { pref[i] = 0; if(a[i] < a[i+1])pref[i] ++; } else if(i == n-1) { pref[i] = pref[i-1]; if(a[i] < a[i-1])pref[i] ++; } else { pref[i] = pref[i-1]; if(a[i] < a[i+1] && a[i] < a[i-1])pref[i] ++; } } } int last[maxn], nxt[maxn]; int active[maxn]; /// shtoto ako imame po malko ot strani ne mojem da go vzemem zaedno s tekushtoto /// a ako trqbva da izbirame iskame po malkoto /// taka che vzimame po malkoto?? int max_towers(int L, int R, int D) { if(D == 1) { int sz = R - L + 1; int ans = 0; if(L == R)return 1; if(sz > 2) { ans += pref[R-1] - pref[L]; } if(L < n-1 && a[L] < a[L+1])ans ++; if(R > 0 && a[R] < a[R-1])ans ++; return ans; } 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...