Submission #850917

#TimeUsernameProblemLanguageResultExecution timeMemory
850917DextarRadio Towers (IOI22_towers)C++17
29 / 100
4018 ms26912 KiB
#include <cstdio> #ifdef DEBUG #define D(X) X #else #define D(X) #endif #include <bits/stdc++.h> #define fr first #define sc second #define ll long long #define pi 3.14159265359 #define pub push_back #define pob pop_back #define pari pair<int,int> #define parli pair<long, long> using namespace std; const int INF = 1000 * 1000 * 1000; const ll INF2 = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000; const int mod = 1000 * 1000 * 1000 + 7; bool comp(pari& v1, pari& v2) { return v1.fr < v2.fr; } struct seg { vector<int> tree; int sz; void build(int n) { sz = 1; while(sz<n) { sz *= 2; } tree.resize(2*sz + 1, 0); } void clean() { for(int i=0; i<tree.size(); i++) { tree[i] = 0; } } void recSet(int idx, int lx, int rx, int i, int val) { if(rx-lx==1) { tree[idx] = val; return; } int mid = (lx+rx)/2; if(i<mid) { recSet(2*idx+1, lx, mid, i, val); } else { recSet(2*idx+2, mid, rx, i, val); } tree[idx] = max(tree[2*idx+1], tree[2*idx+2]); } void setX(int i, int val) { recSet(0, 0, sz, i, val); } int rec_range(int idx, int lx, int rx, int l, int r) { if(lx>=l&&rx<=r) { return tree[idx]; } if(rx<=l||lx>=r) return 0; int mid = (lx+rx)/2; int left = rec_range(2*idx+1, lx, mid, l, r); int right = rec_range(2*idx+2, mid, rx, l, r); return max(left, right); } int range(int l, int r) { if(l>=r) { return 0; } return rec_range(0, 0, sz, l, r); } }; struct seg2 { vector<int> tree; int sz; void build(int n) { sz = 1; while(sz<n) { sz *= 2; } tree.resize(2*sz + 1, INF); } void clean() { for(int i=0; i<tree.size(); i++) { tree[i] = INF; } } void recSet(int idx, int lx, int rx, int i, int val) { if(rx-lx==1) { tree[idx] = val; return; } int mid = (lx+rx)/2; if(i<mid) { recSet(2*idx+1, lx, mid, i, val); } else { recSet(2*idx+2, mid, rx, i, val); } tree[idx] = min(tree[2*idx+1], tree[2*idx+2]); } void setX(int i, int val) { recSet(0, 0, sz, i, val); } int rec_range(int idx, int lx, int rx, int l, int r) { if(lx>=l&&rx<=r) { return tree[idx]; } if(rx<=l||lx>=r) return INF; int mid = (lx+rx)/2; int left = rec_range(2*idx+1, lx, mid, l, r); int right = rec_range(2*idx+2, mid, rx, l, r); return min(left, right); } int range(int l, int r) { return rec_range(0, 0, sz, l, r); } int low1(int idx, int lx, int rx, int l, int r, int val, int dir) { if(tree[idx]>=val||l>=rx||lx>=r) { if(dir==0) return -1; return INF; } if(rx-lx==1) { return lx; } int mid = (lx+rx)/2; int id1 = low1(2*idx+1, lx, mid, l, r, val, dir); int id2 = low1(2*idx+2, mid, rx, l, r, val, dir); if(dir==0) { return max(id1, id2); } return min(id1, id2); } int low1(int l, int r, int val, int dir) { return low1(0, 0, sz, l, r, val, dir); } }; vector<int> dp; seg mint, maxt, st2; map<int, int> ord; vector<int> h; int res = 0; int center = -1; vector<int> pref, left1, right1, difh; int qcnt = 0; seg2 st1; void init2(int l, int r, int d) { int n = h.size(); res = 0; for(int i=0; i<=n; i++) { dp[i] = 0; } vector<int> used(n+1, 0); vector<int> nums; for(int i=l; i<=r; i++) { int f1 = 0, f2 = 0; nums.pub(h[i]); nums.pub(h[i]-d); nums.pub(h[i]+d); if(i>l) { if(h[i]>=h[i-1]) { f1 = 1; } else { f1 = 2; } } if(i<r) { if(h[i]>=h[i+1]) { f2 = 1; } else { f2 = 2; } } if(f1==0) { f1 = f2; } if(f2==0) { f2 = f1; } if(f1==f2) { used[i] = f1; } } sort(nums.begin(), nums.end()); ord.clear(); ord[nums[0]] = 0; int sz = nums.size(); for(int i=1; i<sz; i++) { if(nums[i]>nums[i-1]) { ord[nums[i]] = ord[nums[i-1]] + 1; } else { ord[nums[i]] = ord[nums[i-1]]; } } mint.clean(); maxt.clean(); mint.build(sz); maxt.build(sz); for(int i=r; i>=l; i--) { if(used[i]==0) { continue; } if(used[i]==1&&h[i]-d>0) { dp[i] = mint.range(0, ord[h[i]-d] + 1); maxt.setX(ord[h[i]], dp[i]); } if(used[i]==2) { dp[i] = 1 + maxt.range(ord[h[i]+d], sz); mint.setX(ord[h[i]], dp[i]); } res = max(res, dp[i]); } } void calc_pref() { int n = h.size(); pref.resize(n+1); pref[0] = 0; for(int i=1; i<=n; i++) { pref[i] = pref[i-1]; if(i>1&&i<n) { if(h[i-1]<h[i-2]&&h[i-1]<h[i]) { pref[i]++; } } else if(i>1) { if(h[i-1]<h[i-2]) { pref[i]++; } } else { if(h[i-1]<h[i]) { pref[i]++; } } } } void all_arr() { int n = h.size(); left1.resize(n, INF); right1.resize(n, -1); st1.build(n); st2.build(n); for(int i=0; i<n; i++) { st1.setX(i, h[i]); st2.setX(i, h[i]); } difh.resize(n); for(int i=0; i<n; i++) { pari p = {h[i], i}; left1[p.sc] = st1.low1(0, p.sc, p.fr, 0); right1[p.sc] = st1.low1(p.sc + 1, n, p.fr, 1); int h1 = 2*INF+10, h2 = h1; if(left1[p.sc]!=-1) { h1 = st2.range(left1[p.sc]+1, p.sc); } if(right1[p.sc]!=INF) { h2 = st2.range(p.sc+1, right1[p.sc]); } //cout<<h1<<endl; difh[p.sc] = min(h1, h2) - p.fr; } sort(difh.begin(), difh.end()); } void init(int n, vector<int> h2) { h.resize(n); for(int i=0; i<n; i++) { h[i] = h2[i]; } dp.resize(n+1); int idx = 1; while(idx<n&&h[idx]>=h[idx-1]) { idx++; } center = idx - 1; while(idx<n&&h[idx]<=h[idx-1]) { idx++; } calc_pref(); if(idx==n) { return; } center = -1; init2(0, n - 1, 1); } int max_towers(int l, int r, int d) { qcnt++; int n = h.size(); if(n==1) { return 1; } if(l==r) { return 1; } if(center!=-1) { if(r<=center||l>=center) { return 1; } if(h[center]-h[l]>=d&&h[center]-h[r]>=d) { return 2; } return 1; } if(d==1) { if(qcnt==1) { calc_pref(); } int ans = pref[r] - pref[l+1]; if(h[l]<h[l+1]) { ans++; } if(h[r]<h[r-1]) { ans++; } return ans; } /* for(int i=0; i<n; i++) { //cout<<left1[i]<<" "; //cout<<right1[i]<<" "; //cout<<difh[i]<<" "; } //cout<<endl; */ if(l==0&&r==h.size()-1) { if(qcnt==1) { all_arr(); } int lo = 0, hi = n - 1; while(lo<=hi) { int mid = (lo+hi)/2; if(difh[mid]>=d) { hi = mid - 1; } else { lo = mid + 1; } } return n - lo; } if(qcnt==1) { qcnt = 7; init2(l, r, d); return res; } return res; } /* 7 10 20 60 40 50 30 70 */ /* int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //D(freopen("input.txt","r",stdin);) //D(freopen("ouput.txt","w",stdout);) int t = 1; //cin >> t; loop: while(t--) { int n; cin >> n; vector<int> a(n); for(int i=0; i<n; i++) { cin >> a[i]; } init(n, a); int res = max_towers(0, 6, 10); if(res==0) { res = 1; } cout << res; } return 0; } */

Compilation message (stderr)

towers.cpp: In member function 'void seg::clean()':
towers.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |           for(int i=0; i<tree.size(); i++) {
      |                        ~^~~~~~~~~~~~
towers.cpp: In member function 'void seg2::clean()':
towers.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |           for(int i=0; i<tree.size(); i++) {
      |                        ~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:366:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  366 |     if(l==0&&r==h.size()-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...