oj.uz

Submission #388677

# Submission time Handle Problem Language Result Execution time Memory
388677 2021-04-12T15:01:34 Z phathnv 3D Histogram (COCI20_histogram) C++11
110 / 110
 711 ms 27512 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Histogram"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> point;

const int N = 2e5 + 1;

point operator - (const point &a, const point &b){
    return point(a.X - b.X, a.Y - b.Y);
}

ll operator * (const point &a, const point &b){
    return (ll) a.X * b.Y - (ll) a.Y * b.X;
}

bool CW(point &a, point &b, point &c){
    return (b - a) * (c - b) < 0;
}

struct convexHull{
    vector <point> d;
    int ptr = -1;
    void reset(){
        d.clear();
    }
    void add(point p){
        while (d.size() > 1 && !CW(d[d.size() - 2], d[d.size() - 1], p))
            d.pop_back();
        d.push_back(p);
        ptr = d.size() - 1;
    }
    ll findMax(point a){
        if (d.empty())
            return 0;
        while (ptr > 0 && a * d[ptr] < a * d[ptr - 1])
            ptr--;
        return a * d[ptr];
    }
} cvh;

struct segmentTree{
    convexHull d[N * 2];
    void reset(int id, int l, int r){
        d[id].reset();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        reset(id << 1, l, mid);
        reset(id << 1 | 1, mid + 1, r);
    }
    void add(int id, int l, int r, int pos, point p){
        if (pos < l || r < pos)
            return;
        d[id].add(p);
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        add(id << 1, l, mid, pos, p);
        add(id << 1 | 1, mid + 1, r, pos, p);
    }
    ll getMax(int id, int l, int r, int u, int v, point p){
        if (v < l || r < u || u > v)
            return 0;
        if (u <= l && r <= v)
            return d[id].findMax(p);
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v, p), getMax(id << 1 | 1, mid + 1, r, u, v, p));
    }
} ST;

int n, a[N], b[N];

int minA[N], minB[N], x[N], y[N];

void readInput(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &a[i], &b[i]);
}

ll calc(int l, int r, int d){
    if (l > r)
        return 0;

    int mid = (l + r + d) >> 1;
    minA[mid] = a[mid];
    minB[mid] = b[mid];
    for(int i = mid + 1; i <= r; i++){
        minA[i] = min(minA[i - 1], a[i]);
        minB[i] = min(minB[i - 1], b[i]);
    }
    for(int i = mid - 1; i >= l; i--){
        minA[i] = min(minA[i + 1], a[i]);
        minB[i] = min(minB[i + 1], b[i]);
    }

    ll res = 0;
    int ptr;
    /// minA and minB in left
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minA[cur] <= minA[ptr] && minB[cur] <= minB[ptr])
            ptr++;
        res = max(res, (ll) (ptr - cur) * minA[cur] * minB[cur]);
    }
    /// minA in left and minB in right
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minA[cur] <= minA[ptr])
            ptr++;
        y[cur] = ptr - 1;
    }
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minB[cur] < minB[ptr])
            ptr++;
        x[cur] = ptr;
    }

    ST.reset(1, mid, r);
    for(int j = r; j >= mid; j--)
        ST.add(1, mid, r, j, point(minB[j], (ll) minB[j] * j));
    for(int i = l; i <= mid; i++)
        res = max(res, ST.getMax(1, mid, r, x[i], y[i], point(minA[i], (ll) minA[i] * (i - 1))));

    res = max(res, calc(l, mid - 1, d));
    res = max(res, calc(mid + 1, r, d));

    return res;
}

void solve(){
    ll res = 0;
    res = max(res, calc(1, n, 0));
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + n);
    res = max(res, calc(1, n, 1));
    printf("%lld", res);
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message

histogram.cpp: In function 'void readInput()':
histogram.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
histogram.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d %d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12876 KB Output is correct
2 Correct 15 ms 12924 KB Output is correct
3 Correct 10 ms 12968 KB Output is correct
4 Correct 14 ms 12964 KB Output is correct
5 Correct 10 ms 12980 KB Output is correct
6 Correct 11 ms 12980 KB Output is correct
7 Correct 10 ms 12876 KB Output is correct
8 Correct 10 ms 12876 KB Output is correct
9 Correct 10 ms 12984 KB Output is correct
10 Correct 10 ms 12876 KB Output is correct
11 Correct 6 ms 12748 KB Output is correct
12 Correct 10 ms 12940 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12876 KB Output is correct
2 Correct 15 ms 12924 KB Output is correct
3 Correct 10 ms 12968 KB Output is correct
4 Correct 14 ms 12964 KB Output is correct
5 Correct 10 ms 12980 KB Output is correct
6 Correct 11 ms 12980 KB Output is correct
7 Correct 10 ms 12876 KB Output is correct
8 Correct 10 ms 12876 KB Output is correct
9 Correct 10 ms 12984 KB Output is correct
10 Correct 10 ms 12876 KB Output is correct
11 Correct 6 ms 12748 KB Output is correct
12 Correct 10 ms 12940 KB Output is correct
13 Correct 659 ms 25324 KB Output is correct
14 Correct 669 ms 27512 KB Output is correct
15 Correct 682 ms 25448 KB Output is correct
16 Correct 676 ms 25484 KB Output is correct
17 Correct 629 ms 26972 KB Output is correct
18 Correct 668 ms 27328 KB Output is correct
19 Correct 711 ms 26952 KB Output is correct
20 Correct 660 ms 27432 KB Output is correct
21 Correct 703 ms 25504 KB Output is correct
22 Correct 694 ms 27512 KB Output is correct
23 Correct 55 ms 14060 KB Output is correct
24 Correct 682 ms 25324 KB Output is correct