oj.uz

Submission #1068744

# Submission time Handle Problem Language Result Execution time Memory
1068744 2024-08-21T11:47:09 Z Unforgettablepl Radio Towers (IOI22_towers) C++17
0 / 100
 659 ms 36284 KB 
#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;
            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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 31616 KB 31st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26712 KB Output is correct
2 Incorrect 18 ms 26968 KB 1st lines differ - on the 1st token, expected: '292', found: '262092'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26712 KB Output is correct
2 Incorrect 18 ms 26968 KB 1st lines differ - on the 1st token, expected: '292', found: '262092'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 659 ms 36284 KB 1st lines differ - on the 1st token, expected: '11903', found: '242973'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 235 ms 28912 KB 1st lines differ - on the 1st token, expected: '7197', found: '262144'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26712 KB Output is correct
2 Incorrect 18 ms 26968 KB 1st lines differ - on the 1st token, expected: '292', found: '262092'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 31616 KB 31st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -