oj.uz

Submission #960770

# Submission time Handle Problem Language Result Execution time Memory
960770 2024-04-11T03:19:57 Z Zero_OP Lightning Conductor (POI11_pio) C++14
27 / 100
 1000 ms 65536 KB 
#include<bits/stdc++.h>

using namespace std;

struct MaxFetcher{
    priority_queue<int> a, b;

    void add(int x){ a.push(x); }
    void remove(int x){ b.push(x); }
    int get_max(){
        while(!b.empty() && a.top() == b.top()) a.pop(), b.pop();
        return (a.empty() ? 0 : a.top());
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; ++i){
        cin >> h[i];
    }

    vector<int> prefix(n), suffix(n), ceil_sqrt(n);
    for(int i = 0; i < n; ++i){
        int l = 0, r = 1000, ans = 0;
        while(l <= r){
            int mid = l + r >> 1;
            if(mid * mid >= i) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        ceil_sqrt[i] = ans;
    }

    vector<int> p(n);
    vector<vector<int>> updates(n);

    for(int i = 0; i < n; ++i){ //when ceil_sqrt(i) is decreased
        for(int k = 0; k * k + 1 <= i; ++k){
            updates[i - k * k - 1].push_back(i); 
        }
    }
    
    auto solve = [&](){
        vector<int> cur = ceil_sqrt;
        MaxFetcher fetcher;
        for(int i = 0; i < n; ++i){
            fetcher.add(h[i] + ceil_sqrt[i]);
        }

        for(int i = 0; i < n - 1; ++i){
            p[i] = max(p[i], fetcher.get_max() - h[i]);
            for(int j : updates[i]){
                fetcher.remove(h[j] + cur[j]);
                --cur[j];
                if(cur[j] > 0) fetcher.add(h[j] + cur[j]);
            }
        }
    };

    solve();
    reverse(p.begin(), p.end());
    reverse(h.begin(), h.end());
    solve();

    reverse(p.begin(), p.end());
    for(int i = 0; i < n; ++i) cout << p[i] << '\n';
    
    return 0;
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:30:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -