Submission #8280444


Source Code Expand

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

using namespace std;
using namespace __gnu_pbds;

#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

struct int_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    size_t operator()(pii x) const {
        return int_hash{}(x.first) ^ (int_hash{}(x.second) << 16);
    }
};

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<cd> vcd;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pii>> vvpii;
typedef vector<vector<pll>> vvpll;
typedef unordered_map<int, int, int_hash> umpii;
typedef unordered_map<ll, ll, int_hash> umpll;
typedef unordered_set<int, int_hash> usi;
typedef unordered_set<ll, int_hash> usll;
typedef unordered_set<pii, pair_hash> uspii;
typedef queue<int> qi;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = numeric_limits<int>::max();
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n; cin >> n;
    vpll v(n, {0LL, 0LL});
    F0R(i, n) cin >> v[i].f >> v[i].s;
    sort(begin(v), end(v));

    ll l = v[0].s;
    multiset<ll> ms;
    for(ll i = 1; i < n; i++) {
        ms.insert(v[i].s);
    }

    ll best = 0LL;
    for(ll i = 1; i < n; i++) {
        best = max(best, max(0LL, l - v[i - 1].f + 1LL) + max(0LL, *ms.begin() - v.back().f + 1LL));
        l = min(l, v[i].s);
        ms.erase(ms.find(v[i].s));
    }

    for(int i = 0; i < n; i++) {
        best = max(best, v[i].s - v[i].f + 1);
    }
    cout << best << endl;
}

Submission Info

Submission Time
Task B - Two Contests
User Tsugiru
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2849 Byte
Status
Exec Time 79 ms
Memory 6528 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 600 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt
Case Name Status Exec Time Memory
00-sample-01.txt 1 ms 256 KB
00-sample-02.txt 1 ms 256 KB
00-sample-03.txt 1 ms 256 KB
01-01.txt 1 ms 256 KB
01-02.txt 31 ms 3072 KB
01-03.txt 35 ms 3328 KB
01-04.txt 38 ms 3584 KB
01-05.txt 28 ms 3712 KB
01-06.txt 17 ms 2560 KB
01-07.txt 2 ms 384 KB
01-08.txt 44 ms 5504 KB
01-09.txt 4 ms 768 KB
01-10.txt 48 ms 6016 KB
01-11.txt 50 ms 6272 KB
01-12.txt 3 ms 512 KB
01-13.txt 42 ms 5376 KB
01-14.txt 37 ms 4864 KB
01-15.txt 7 ms 1152 KB
01-16.txt 15 ms 2304 KB
01-17.txt 77 ms 6528 KB
01-18.txt 79 ms 6528 KB
01-19.txt 78 ms 6528 KB
01-20.txt 54 ms 6528 KB
01-21.txt 53 ms 6528 KB
01-22.txt 55 ms 6528 KB
01-23.txt 54 ms 6528 KB
01-24.txt 53 ms 6528 KB
01-25.txt 54 ms 6528 KB
01-26.txt 53 ms 6528 KB
01-27.txt 54 ms 6528 KB
01-28.txt 53 ms 6528 KB
01-29.txt 54 ms 6528 KB
01-30.txt 53 ms 6528 KB
01-31.txt 53 ms 6528 KB