Submission #751656

#	Time	Username	Problem	Language	Result	Execution time	Memory
751656		worthytacos	Art Exhibition (JOI18_art)	C++14	100 / 100	214 ms	27044 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pll;
/*
cari Sum(R) - Sum(L-1) - W[R]+W[L];
= W[L] - Sum(L-1) + sum(r)-W[R];
1. hitung semua nilai Sum{i} - W[i];
Multi set>> pop setelah dipakai (L);
2. loop semua L, tambah jawaban untuk semua
*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    vector<pair<ll, ll>> rocks(n + 1); // w, v
    rocks[0] = {0, 0};
    for (int i = 1; i <= n; i++)
    {
        cin >> rocks[i].first >> rocks[i].second;
    }
    sort(rocks.begin(), rocks.end());
    for (int i = 1; i <= n; i++)
    {
        rocks[i].second += rocks[i - 1].second;
    }
    // cari max val of (Vi - Wi) - (Vj-1 - Wj); j > i;
    // (Vi - Vj-1) - (Wi - Wj) > max;
    // Vi - Vj-1 - Wi + Wj
    // Vi - Wi - Vj-w + Wj > max;
    // i > j
    // n <= 500 000??
    // maka nilai f(j) = (Vj-1 - Wj) harus minimal, berarti jika ada j1 and j2 such that j1 > j2 && f(j1)<f(j2);
    // j2 becomes useless;
    vector<ll> minFVal;
    vector<ll> theJidx;
    for (int j = n; j >= 1; j--)
    {
        ll f = rocks[j - 1].second - rocks[j].first;
        if (minFVal.empty())
        {
            minFVal.push_back(f);
            theJidx.push_back(j);
        }
        else
        {
            ll lobo = lower_bound(minFVal.begin(), minFVal.end(), f) - minFVal.begin();
            if (lobo == minFVal.size())
            {
                minFVal.push_back(f);
                theJidx.push_back(j);
            }
            else
            {
                while (lobo != minFVal.size() - 1)
                {
                    minFVal.pop_back();
                    theJidx.pop_back();
                }
                minFVal[lobo] = f;
                theJidx[lobo] = j;
            }
        }
    }

    ll curJ = theJidx.size() - 1, ans = 0;
    // for (int i = 0; i <= curJ; i++)
    // {
    //     cout << minFVal[i] << " " << theJidx[i] << "\n";
    // }
    for (int i = 1; i <= n; i++)
    {
        ll g = rocks[i].second - rocks[i].first;
        while (curJ > 0 && theJidx[curJ - 1] <= i)
        {
            curJ--;
        }
        ans = max(ans, g - minFVal[curJ]);
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:50:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (lobo == minFVal.size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~
art.cpp:57:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 while (lobo != minFVal.size() - 1)
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~

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