Submission #1068734

#TimeUsernameProblemLanguageResultExecution timeMemory
1068734UnforgettableplRadio Towers (IOI22_towers)C++17
0 / 100
665 ms36168 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; const int INF = 2e9; namespace { vector<int> H; int N; bool done = false; vector lift(250000,vector(18,0)); vector leave(250000,0); void generate(int D) { if(done)return; vector<int> L(N+1); { deque<pair<int,int>> q; q.emplace_back(INF,0); for(int i=1;i<=N;i++) { while(q.front().first<=H[i])q.pop_front(); int ans = -1; for(int jump=131072;jump;jump/=2) { if(ans+jump>=q.size())continue; if(q[ans+jump].first<H[i]+D)ans+=jump; } ans++; L[i]=q[ans].second; q.emplace_front(H[i],i); } } vector<int> R(N+1); { deque<pair<int,int>> q; q.emplace_back(INF,N+1); for(int i=N;i;i--) { while(q.front().first<=H[i])q.pop_front(); int ans = -1; for(int jump=131072;jump;jump/=2) { if(ans+jump>=q.size())continue; if(q[ans+jump].first<H[i]+D)ans+=jump; } ans++; R[i]=q[ans].second; q.emplace_front(H[i],i); } } int min_node_direct = N+N+1; int min_node_sub = N+N+1; int min_node_leave = N+N+1; vector<vector<int>> q(N+1); vector<vector<int>> ql(N+1); for(int i=N;i;i--) { for(int&j:q[i]) { min_node_direct = min(min_node_direct,j); min_node_sub = min(min_node_sub,j); } for(int&j:ql[i]) { min_node_leave= min(min_node_leave,j); } min_node_direct=min(min_node_direct,R[i]); leave[i]=min_node_leave; lift[i+N][0]=min_node_direct; lift[i][0]=min_node_sub; q[L[i]].emplace_back(R[i]); ql[L[i]].emplace_back(i); } lift[N+N+1][0]=N+N+1; for(int bit=1;bit<18;bit++) { for(int i=1;i<=2*N+1;i++) { lift[i][bit] = lift[lift[i][bit-1]][bit-1]; } } done = true; } } void init(int N,vector<int> H){ H.emplace(H.begin(),-1); ::H = H; ::N = N; } int max_towers(int L,int R,int D){ L++;R++; generate(D); int x = N+L; if(lift[x][0]>R)return 1; int ans = 0; for(int bit=17;bit>=0;bit--) { if(lift[x][bit]<=R) { ans+=(1<<bit); x=lift[x][bit]; } } if(x!=R and leave[x]<=R)ans++; return ans; }

Compilation message (stderr)

towers.cpp: In function 'void {anonymous}::generate(int)':
towers.cpp:23:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |                     if(ans+jump>=q.size())continue;
      |                        ~~~~~~~~^~~~~~~~~~
towers.cpp:39:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                     if(ans+jump>=q.size())continue;
      |                        ~~~~~~~~^~~~~~~~~~
#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...