oj.uz

Submission #1039108

# Submission time Handle Problem Language Result Execution time Memory
1039108 2024-07-30T12:59:24 Z Irate Lightning Conductor (POI11_pio) C++17
72 / 100
 1000 ms 48624 KB 
#include<bits/stdc++.h>
using namespace std;
struct SparseTable{
    vector<int>LOG;
    vector<vector<int>>sTable;
    SparseTable(vector<int>&v){
        int n = (int)v.size();
        LOG.resize(n + 1);
        LOG[1] = 0;
        for(int i = 2;i <= n;++i){
            LOG[i] = LOG[i / 2] + 1;
        }
        sTable.resize(LOG[n] + 1);
        for(int i = 0;i <= LOG[n];++i){
            sTable[i].resize(n);
        }
        for(int i = 0;i < n;++i){
            sTable[0][i] = v[i];
        }
        for(int i = 1;i <= LOG[n];++i){
            for(int j = 0;j + (1 << (i - 1)) < n;++j){
                sTable[i][j] = max(sTable[i - 1][j], sTable[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    int Max(int l, int r){
        int lg = LOG[r - l + 1];
        return max(sTable[lg][l], sTable[lg][r - (1 << lg) + 1]);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i = 0;i < n;++i){
        cin >> v[i];
    }
    SparseTable table(v);
    for(int i = 0;i < n;++i){
        int l = i + 1, p = 0;
        for(int j = 1;;++j){
            int r = min(n - 1, i + j * j);
            if(l >= n)break;
            p = max(p, table.Max(l, r) + j - v[i]);
            l = r + 1;
        }
        l = i - 1;
        for(int j = 1;;++j){
            int r = max(0, i - j * j);
            if(l < 0)break;
            p = max(p, table.Max(r, l) + j - v[i]);
            l = r - 1;
        }
        cout << p << '\n';
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2924 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4816 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5968 KB Output is correct
2 Correct 81 ms 5212 KB Output is correct
3 Correct 83 ms 5920 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 9004 KB Output is correct
2 Correct 156 ms 9020 KB Output is correct
3 Correct 136 ms 9296 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 21584 KB Output is correct
2 Correct 581 ms 21204 KB Output is correct
3 Correct 574 ms 21328 KB Output is correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1025 ms 36136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 48624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1034 ms 47736 KB Time limit exceeded
2 Halted 0 ms 0 KB -