Submission #1068750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068750		Unforgettablepl	Radio Towers (IOI22_towers)	C++17	56 / 100	820 ms	39268 KiB

towers

#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+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;
            assert(min_node_sub>i);
            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;
      |                        ~~~~~~~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23