제출 #971225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971225		vyshniak_n	Art Exhibition (JOI18_art)	C++17	100 / 100	421 ms	36952 KiB

art

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma target("avx,avx2")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef long double ld;

using namespace std;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define popb pop_back
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll N = 5e5 + 10;
const ll INF = 2e18 + 10;
const ll inf = 2e9 + 10;

ll t[4 * N], lazy[4 * N];
void push(ll v) {
    t[v << 1] += lazy[v];
    t[v << 1 | 1] += lazy[v];

    lazy[v << 1] += lazy[v];
    lazy[v << 1 | 1] += lazy[v];

    lazy[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll val) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && r >= tr) {
        t[v] += val;
        lazy[v] += val;
        return;
    } 

    push(v);
    ll tm = (tl + tr) >> 1;

    upd(v << 1, tl, tm, l, r, val);
    upd(v << 1 | 1, tm + 1, tr, l, r, val);

    t[v] = max(t[v << 1], t[v << 1 | 1]);
}
ll get(ll v, ll tl, ll tr, ll l, ll r) {
    if (l > tr || r < tl)
        return -INF;
    if (l <= tl && r >= tr)
        return t[v];

    push(v);
    ll tm = (tl + tr) >> 1;

    return max(get(v << 1, tl, tm, l, r),
               get(v << 1 | 1, tm + 1, tr, l, r));
}

void solve() {
    ll n;
    cin >> n;

    vector <point> events(n);
    for (ll i = 0; i < n; i++)
        cin >> events[i].ff >> events[i].ss;

    sort(all(events));

    ll ans = -INF;
    for (ll i = 0; i < n; i++) {
        upd(1, 1, n, i + 1, i + 1, events[i].ff);
        upd(1, 1, n, 1, i + 1, events[i].ss);

        ans = max(ans, get(1, 1, n, 1, i + 1) - events[i].ff);
    }

    cout << ans << el;
    return;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--)
        solve();
    return 0;
}

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