oj.uz

Submission #689735

# Submission time Handle Problem Language Result Execution time Memory
689735 2023-01-29T08:39:14 Z lohacho Radio Towers (IOI22_towers) C++17
0 / 100
 1164 ms 31372 KB 
#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;
vector<int> leaf, lt;
vector<vector<int>> spa;
vector<int> lp, rp;
vector<int> mnl, mnr;

struct fenw{
    int n;
    vector<int> tr;

    fenw(int m){
        n = m + 4;
        tr.resize(n, -1);
    }

    void push(int pos, int val){
        for(int i = pos; i < n; i += (i & -i)){
            tr[i] = max(tr[i], val);
        }
    }

    int get(int pos){
        int rv = -1;

        for(int i = pos; i > 0; i -= (i & -i)){
            rv = max(rv, tr[i]);
        }

        return rv;
    }
};

int fir = 0;

void init(int N, std::vector<int> H) {
    n = N;
    a = H;

    spa.resize(n, vector<int>(20, (int)1e9));
    lp.resize(n);
    rp.resize(n);
    mnr.resize(n, (int)1e9);
    mnl.resize(n, (int)1e9);
}

int max_towers(int L, int R, int D) {
    if(!fir){
        fir = 1;
        vector<int> srt;
        for(int i = 0; i < n; ++i){
            srt.push_back(a[i]);
            srt.push_back(a[i] + D);
        }

        sort(srt.begin(), srt.end());
        srt.erase(unique(srt.begin(), srt.end()), srt.end());

        auto getnum = [&](int x)->int{
            return lower_bound(srt.begin(), srt.end(), x) - srt.begin();
        };

        auto getl = [&](vector<int> x)->vector<int>{
            fenw tr((int)srt.size() + 4);
            vector<int> rv(n);

            for(int i = 0; i < n; ++i){
                rv[i] = tr.get((int)srt.size() - getnum(a[i] + D)) + 1;
                rv[i] = i - rv[i];
                tr.push((int)srt.size() - getnum(a[i]), i);
            }

            return rv;
        };

        lp = getl(a);
        reverse(a.begin(), a.end());
        rp = getl(a);
        reverse(a.begin(), a.end());
        reverse(rp.begin(), rp.end());

        // for(int i = 0; i < n; ++i){
        //     cout << i - lp[i] << ' ' << i + rp[i] << endl;
        // }
        // cout << endl;

        for(int i = n - 1; i >= 0; --i){
            assert(i - lp[i] >= 0);
            spa[i - lp[i]][0] = min(spa[i - lp[i]][0], i + rp[i]);
            for(int j = 1; j < 20; ++j){
                if(spa[i][j - 1] < n - 1){
                    spa[i][j] = spa[spa[i][j - 1] + 1][j - 1];
                }
            }
            if(i + 1 < n){
                for(int j = 0; j < 20; ++j){
                    spa[i][j] = min(spa[i][j], spa[i + 1][j]);
                }
            }

            mnl[i - lp[i]] = min(mnl[i - lp[i]], i);
            mnr[i] = i + rp[i];
        }

        for(int i = n - 2; i >= 0; --i){
            mnl[i] = min(mnl[i], mnl[i + 1]);
            mnr[i] = min(mnr[i], mnr[i + 1]);
        }
    }

    int ans = 1;
    int pos = mnr[L] + 1;
    for(int i = 19; i >= 0; --i){
        if(spa[pos][i] < R){
            ans += (1 << i);
            pos = spa[pos][i] + 1;
        }
    }
    if(mnl[pos] <= R){
        ++ans;
    }

    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 18796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Runtime error 2 ms 976 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Runtime error 2 ms 976 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 16620 KB Output is correct
2 Correct 1103 ms 16704 KB Output is correct
3 Correct 1164 ms 16656 KB Output is correct
4 Correct 1113 ms 16652 KB Output is correct
5 Correct 1062 ms 16728 KB Output is correct
6 Correct 1116 ms 16712 KB Output is correct
7 Correct 849 ms 16704 KB Output is correct
8 Correct 829 ms 16700 KB Output is correct
9 Runtime error 80 ms 31372 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 4276 KB 2nd lines differ - on the 1st token, expected: '7063', found: '7197'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Runtime error 2 ms 976 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 18796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -