oj.uz

Submission #333889

# Submission time Handle Problem Language Result Execution time Memory
333889 2020-12-08T02:11:32 Z wiwiho 3D Histogram (COCI20_histogram) C++14
20 / 110
 343 ms 78788 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

int argmin(vector<ll>& a, int x, int y){
    return a[x] < a[y] ? x : y;
}

struct SparseTable{

    vector<vector<int>> st;

    void build(vector<ll>& a){
        int n = a.size();
        st.resize(n, vector<int>(20));
        for(int i = 0; i < n; i++) st[i][0] = i;
        for(int i = 1; i < 20; i++){
            for(int j = 0; j + (1 << i) - 1 < n; j++){
                st[j][i] = argmin(a, st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
            }
        }
    }

    int query(vector<ll>& a, int l, int r){
        int lg = __lg(r - l + 1);
        return argmin(a, st[l][lg], st[r - (1 << lg) + 1][lg]);
    }

};

int n;
vector<ll> a, b;
SparseTable sta, stb;

map<pii, int> tmp;
ll f2(int l, int r){
    if(l > r) return 0;
    if(tmp.find(mp(l, r)) != tmp.end()) return tmp[mp(l, r)];
    int m = stb.query(b, l, r);
    //cerr << l << " " << r << " " << m << "\n";
    tmp[mp(l, r)] = max({b[m] * (r - l + 1), f2(l, m - 1), f2(m + 1, r)});
    return tmp[mp(l, r)];
}

ll f1(int l, int r){
    if(l > r) return 0;
    int m = sta.query(a, l, r);
    return max({a[m] * f2(l, r), f1(l, m - 1), f1(m + 1, r)});
}

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

    cin >> n;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    sta.build(a);
    stb.build(b);
    
    cout << f1(0, n - 1) << "\n";
    
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 4 ms 1356 KB Output is correct
5 Correct 33 ms 5464 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 36 ms 6040 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 972 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 2 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 4 ms 1356 KB Output is correct
5 Correct 33 ms 5464 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 36 ms 6040 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 972 KB Output is correct
13 Correct 343 ms 78788 KB Output is correct
14 Incorrect 253 ms 76160 KB Output isn't correct
15 Halted 0 ms 0 KB -