Submission #699780

#	Time	Username	Problem	Language	Result	Execution time	Memory
699780		Ran	Art Exhibition (JOI18_art)	C++17	100 / 100	309 ms	43468 KiB

art

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const long long N = 5e5 + 100;

int n;

pair <long long, long long> art[N];

long long f[N];

struct segTree
{
    long long st[4 * N], lazy[4 * N];
    segTree()
    {
        for (int i = 0; i < 4 * N; i++)
        {
            st[i] = -1e18;
            lazy[i] = 0;
        }
    }
    void build(int id, int l, int r)
    {
        if (l > r)
            return;
        if (l == r)
        {
            st[id] = f[l] - art[l].fi;
            return;
        }
        int mid = l + r >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }
    void down(int id)
    {
        st[id * 2] += lazy[id];
        st[id * 2 + 1] += lazy[id];
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, long long val)
    {
        if (v < l || r < u)
            return;
        if (u <= l && r <= v)
        {
            lazy[id] += val;
            st[id] += val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }
    long long get(int id, int l, int r, int u, int v)
    {
        if (v < l || r < u)
            return -1e18;
        if (u <= l && r <= v)
            return st[id];
        int mid = l + r >> 1;
        down(id);
        return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
} tree;

void sub3()
{
    long long ans = -1e18;
    for (int i = 1; i <= n; i++)
    {
        long long sum = 0;
        for (int j = i; j <= n; j++)
        {
            sum = sum + art[j].se;
            ans = max(ans, sum - (art[j].fi - art[i].fi));
        }
    }
    cout << ans;
}

void sub()
{
    long long ans = -1e18, sum = 0;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] + art[i].se;
    tree.build(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        long long tmp = tree.get(1, 1, n, i, n);
        ans = max(ans, tmp + art[i].fi);
        tree.update(1, 1, n, i, n, -art[i].se);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> art[i].fi >> art[i].se;
    sort(art + 1, art + 1 + n);
    if (n <= 5000)
        sub3();
    else
        sub();
    return 0;
}

Compilation message (stderr)

art.cpp: In member function 'void segTree::build(int, int, int)':
art.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~
art.cpp: In member function 'void segTree::update(int, int, int, int, int, long long int)':
art.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = l + r >> 1;
      |                   ~~^~~
art.cpp: In member function 'long long int segTree::get(int, int, int, int, int)':
art.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~
art.cpp: In function 'void sub()':
art.cpp:94:28: warning: unused variable 'sum' [-Wunused-variable]
   94 |     long long ans = -1e18, sum = 0;
      |                            ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50