Submission #683801

#	Time	Username	Problem	Language	Result	Execution time	Memory
683801		ghostwriter	Sails (IOI07_sails)	C++17	100 / 100	54 ms	2564 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define bg begin
#define ed end
#define ft front
#define bk back
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define ins insert
#define ers erase
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define str string
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : x)
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Pretty hard greedy problem :v. Rearrange all pair (h, k) in increasing order. Iterate from 1 to n and in each position, choose
    all the smallest value an increase it by 1 (also increase the answer as well). We can proof this with greedy exchange (a lot of greedy exchange) and induction
    but the intuition is to reduce the imbalance between heights.
*/
const int N = 1e5 + 1;
int n;
pi a[N];
pll f[N];
pll operator +(const pll &a, const pll &b) { return {a.st + b.st, a.nd + b.nd}; }
void operator +=(pll &a, const pll &b) { a = a + b; }
void upd(int pos, int v) { for (int i = pos; i < N; i += (i & -i)) { f[i].st += v; f[i].nd += 1LL * pos * v; } }
void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
ll get(int pos) { pll rs = {0, 0}; for (int i = pos; i > 0; i -= (i & -i)) rs += f[i]; return (pos + 1) * rs.st - rs.nd; }
ll get(int l, int r) { return get(r) - get(l - 1); }
int get1(int pos) { int rs = 0; for (int i = pos; i > 0; i -= (i & -i)) rs += f[i].st; return rs; }
pi getp(int x) {
    pll rs = {N, 0}, cur = {0, 0}, sum = {0, 0};
    FSN(i, 17) {
        if (cur.st + (1 << i) < N) {
            ll tmp = cur.st + (1 << i);
            if (sum.st + f[tmp].st == x) rs.st = min(rs.st, tmp);
            else if (sum.st + f[tmp].st > x) {
                cur.st = tmp;
                sum.st += f[tmp].st;
            }
        }
        if (cur.nd + (1 << i) < N) {
            ll tmp = cur.nd + (1 << i);
            if (sum.nd + f[tmp].st == x) {
                rs.nd = max(rs.nd, tmp);
                cur.nd = tmp;
                sum.nd += f[tmp].st;
            }
            else if (sum.nd + f[tmp].st > x) {
                cur.nd = tmp;
                sum.nd += f[tmp].st;
            }
        }
    }
    return rs;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n) cin >> a[i].st >> a[i].nd;
    sort(a + 1, a + 1 + n);
    ll rs = 0;
    FOR(i, 1, n) {
        rs += get(a[i].st - a[i].nd + 1, a[i].st);
        int maxv = get1(a[i].st - a[i].nd + 1);
        pi pos = getp(maxv);
        pos.nd = min(pos.nd, a[i].st);
//        cerr << a[i].st << ' ' << a[i].nd << " ; " << pos.st << ' ' << pos.nd << '\n';
        if (pos.nd + 1 <= a[i].st) upd(pos.nd + 1, a[i].st, 1);
        int rm = a[i].nd - a[i].st + pos.nd;
        if (rm) upd(pos.st, pos.st + rm - 1, 1);
//        cerr << a[i].st << " - " << a[i].nd << " : " << maxv << '\n';
//        cerr << i << " : \n";
//        cerr << pos.st << ' ' << pos.nd << '\n';
//        cerr << rm << '\n';
//        cerr << pos.nd + 1 << ' ' << a[i].st << '\n';
//        cerr << pos.st << ' ' << pos.st + rm - 1 << '\n';
//        cerr << '\n';
    }
    cout << rs;
    return 0;
}
/*
4
3 3
9 1
9 5
3 2

*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10