Submission #1203369

#TimeUsernameProblemLanguageResultExecution timeMemory
1203369Zbyszek99Radio Towers (IOI22_towers)C++20
60 / 100
4021 ms382864 KiB
#include "towers.h" #include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define vl vector<long long> #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll rand(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; const int tree_siz = 1024*256-1; struct node { node* left; node* right; bool is_sons = 0; int oper = 0; ll l = 0; ll r = (1 << 30)-1; void upd_sons() { if(!is_sons) { left = new node; right = new node; left -> l = l; left -> r = (l+r)/2; right -> l = (l+r)/2+1; right -> r = r; } is_sons = 1; } int get_sum(int poz) { int ans = oper; //cout << l << " " << r << " " << oper << " " << poz << " query\n"; if(l != r) { upd_sons(); if(poz <= (l+r)/2) ans += left -> get_sum(poz); else ans += right -> get_sum(poz); } return ans; } void add_seg(int l2, int r2, int w, node& prev_node) { // cout << l << " " << r << " " << l2 << " " << r2 << " " << w << " add\n"; if(l >= l2 && r <= r2) { if(l != r) { prev_node.upd_sons(); is_sons = 1; left = prev_node.left; right = prev_node.right; } oper = prev_node.oper + w; return; } ll left_l = l; ll left_r = (l+r)/2; ll right_l = (l+r)/2+1; ll right_r = r; is_sons = 1; prev_node.upd_sons(); if(left_r < l2 || left_l > r2) { left = prev_node.left; } else { left = new node; left -> l = left_l; left -> r = left_r; left -> oper = prev_node.left->oper; left -> add_seg(l2,r2,w,*prev_node.left); } if(right_r < l2 || right_l > r2) { right = prev_node.right; } else { right = new node; right -> l = right_l; right -> r = right_r; right -> oper = prev_node.right->oper; right -> add_seg(l2,r2,w,*prev_node.right); } } }; struct mmtree { pii dmax[tree_siz+1]; pii dmin[tree_siz+1]; void setup(vi arr) { rep(i,siz(arr)) { dmax[tree_siz/2+1+i] = {arr[i],i}; dmin[tree_siz/2+1+i] = {arr[i],i}; } rep2(i,tree_siz/2+1+siz(arr),tree_siz) { dmax[i] = {-2e9,i}; dmin[i] = {2e9,i}; } for(int i = tree_siz/2; i >= 1; i--) { dmax[i] = max(dmax[i*2],dmax[i*2+1]); dmin[i] = min(dmin[i*2],dmin[i*2+1]); } } pair<pii,pii> query(int akt, int p1, int p2, int s1, int s2) { if(p2 < s1 || p1 > s2) return {{2e9,1},{-2e9,1}}; if(p1 >= s1 && p2 <= s2) return {dmin[akt],dmax[akt]}; pair<pii,pii> w1 = query(akt*2,p1,(p1+p2)/2,s1,s2); pair<pii,pii> w2 = query(akt*2+1,(p1+p2)/2+1,p2,s1,s2); return {min(w1.ff,w2.ff),max(w1.ss,w2.ss)}; } pair<pii,pii> get_info(int l, int r) { return query(1,0,tree_siz/2,l,r); } }; int n; int left_D[100'001]; int right_D[100'001]; mmtree mtree; node trees[100'001]; void init(int N, vi H) { n = N; mtree.setup(H); vector<pii> sort_poz; rep(i,n) sort_poz.pb({H[i],i}); sort(all(sort_poz)); set<int> s; forall(it,sort_poz) { auto ptr = s.lower_bound(it.ss); if(ptr == s.end()) { right_D[it.ss] = 1e9; } else { int nxt = *ptr; int max_ = mtree.get_info(it.ss,nxt-1).ss.ff; right_D[it.ss] = max_ - it.ff; } if(ptr == s.begin()) { left_D[it.ss] = 1e9; } else { ptr--; int prev = *ptr; int max_ = mtree.get_info(prev+1,it.ss).ss.ff; left_D[it.ss] = max_-it.ff; } s.insert(it.ss); } rep(i,n) { int min_d = min(left_D[i],right_D[i]); trees[i+1].add_seg(0,min_d,1,trees[i]); } } int max_towers(int L, int R, int D) { int beg_val = trees[L].get_sum(D); int end_val = trees[R+1].get_sum(D); int ans = end_val - beg_val; int first_ = 1e9; int last_ = 0; if(ans == 0) { int min_poz = mtree.get_info(L,R).ff.ss; ans++; last_ = min_poz; first_ = min_poz; } else { int l = L; int r = R; while(l <= r) { int mid = (l+r)/2; if(trees[mid+1].get_sum(D) - beg_val >= 1) { first_ = mid; r = mid-1; } else { l = mid+1; } } l = L; r = R; while(l <= r) { int mid = (l+r)/2; if(end_val - trees[mid].get_sum(D) >= 1) { last_ = mid; l = mid+1; } else { r = mid-1; } } } rep2(i,L,first_-1) { if(right_D[i] >= D) { ans++; break; } } rep2(i,last_+1,R) { if(left_D[i] >= D) { ans++; break; } } return ans; }
#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...