oj.uz

Submission #689729

# Submission time Handle Problem Language Result Execution time Memory
689729 2023-01-29T08:28:41 Z lohacho Radio Towers (IOI22_towers) C++17
0 / 100
 945 ms 39544 KB 
#include "towers.h"

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

int n;
vector<int> a;
vector<int> leaf, lt;
vector<vector<int>> spa, spa2, spa3;
vector<int> lp, rp;
vector<int> mn;

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));
    spa2.resize(n, vector<int>(20, (int)1e9));
    spa3.resize(n, vector<int>(20, (int)1e9));
    lp.resize(n);
    rp.resize(n);
    mn.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){
            spa[i][0] = i + rp[i];
            for(int j = 1; j < 20; ++j){
                if(spa[i][j - 1] < n - 1){
                    spa[i][j] = spa2[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]);
                }
                for(int j = 0; j < 20; ++j){
                    spa2[i][j] = min(spa2[i][j], spa2[i + 1][j]);
                }
            }
            for(int j = 0; j < 20; ++j){
                spa2[i - lp[i]][j] = min(spa2[i - lp[i]][j], spa[i][j]);
            }

            mn[i - lp[i]] = min(mn[i - lp[i]], i);
        }

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

    int ans = 0;
    int pos = L, f = 1;
    for(int i = 19; i >= 0; --i){
        if(f){
            if(spa[pos][i] <= R){
                ans += (1 << i);
                pos = spa[pos][i] + 1;
            }
            f = 0;
        }
        else{
            if(spa2[pos][i] <= R){
                ans += (1 << i);
                pos = spa2[pos][i] + 1;
            }
        }
    }
    if(!ans) ans = 1;
    else{
        if(pos <= R){
            if(mn[pos] <= R){
                ++ans;
            }
        }
    }

    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 454 ms 23896 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
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 3 ms 1100 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 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 3 ms 1100 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 945 ms 39544 KB 21st lines differ - on the 1st token, expected: '20816', found: '20815'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 9804 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 3 ms 1100 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 2 ms 976 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 3 ms 976 KB Output is correct
7 Incorrect 2 ms 976 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 454 ms 23896 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -