제출 #1179983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179983		anteknne	Art Exhibition (JOI18_art)	C++20	100 / 100	386 ms	24872 KiB

art

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

vector<pll> v;
const int MAXN = 500 * 1000;
ll maxx[MAXN * 4];
ll dodaj[MAXN * 4];

void szykuj(int i) {
    dodaj[2 * i] += dodaj[i];
    maxx[2 * i] += dodaj[i];
    dodaj[2 * i + 1] += dodaj[i];
    maxx[2 * i + 1] += dodaj[i];
    dodaj[i] = 0;
}

void aktualizuj (ll x, int a, int b, int a2, int b2, int i) {
    if (b < a2 || a > b2) {
        return;
    }
    if (a <= a2 && b2 <= b) {
        dodaj[i] += x;
        maxx[i] += x;
        return;
    }
    szykuj(i);
    int sr = (a2 + b2)/2;
    aktualizuj(x, a, b, a2, sr, i * 2);
    aktualizuj(x, a, b, sr + 1, b2, i * 2 + 1);
    maxx[i] = max(maxx[i * 2], maxx[i * 2 + 1]);
}

ll odczytaj (int a, int b, int a2, int b2, int i) {
    if (b < a2 || a > b2) {
        return (-1);
    }
    if (a <= a2 && b2 <= b) {
        return maxx[i];
    }
    szykuj(i);
    int sr = (a2 + b2)/2;
    int akt = max(odczytaj(a, b, a2, sr, i * 2), odczytaj(a, b, sr + 1, b2, i * 2 + 1));
    maxx[i] = max(maxx[i * 2], maxx[i * 2 + 1]);
    return akt;
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    pll x;
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> x.st >> x.nd;
        v.pb(x);
    }

    sort(v.begin(), v.end());

    ll suma = 0;

    for (int i = 0; i < n; i ++) {
        suma += v[i].nd;
        aktualizuj(suma - (v[i].st - v[0].st), i, i, 0, n - 1, 1);
    }

    ll wyn = odczytaj(0, n - 1, 0, n - 1, 1);

    for (int i = 1; i < n; i ++) {
        aktualizuj(v[i].st - v[i - 1].st - v[i - 1].nd, i, n - 1, 0, n - 1, 1);
        wyn = max(wyn, odczytaj(0, n - 1, 0, n - 1, 1));
    }
    cout << wyn << "\n";

    return 0;
}

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