Submission #766353

#	Time	Username	Problem	Language	Result	Execution time	Memory
766353		GrindMachine	Sails (IOI07_sails)	C++17	100 / 100	167 ms	8048 KiB

sails

// Om Namah Shivaya

#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;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://github.com/stefdasca/CompetitiveProgramming/blob/master/IOI/IOI%2007-sails.cpp
https://csacademy.com/contest/round-41/task/candles/solution/
https://csacademy.com/submission/386370

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        ll mn,mx;
    };

    struct lazy {
        ll a;
    };

    data d_neutral = {inf2,-inf2};
    lazy l_neutral = {0};

    void merge(data &curr, data &left, data &right) {
        curr.mn = min(left.mn,right.mn);
        curr.mx = max(left.mx,right.mx);
    }

    void create(int x, int lx, int rx, T v) {
        tr[x] = {0,0};
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].a = v;
    }

    void propagate(int x, int lx, int rx) {
        ll v = lz[x].a;
        if(!v) return;

        tr[x].mn += v;
        tr[x].mx += v;

        if(rx-lx > 1){
            lz[2*x+1].a += v;
            lz[2*x+2].a += v;
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, 0);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(n, 2 * x + 1, lx, mid);
        build(n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(int n) {
        build(n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }

    int find_first(int x, int lx, int rx, int v){
        propagate(x,lx,rx);
        if(tr[x].mn > v) return -1;
        if(tr[x].mx < v) return -1;
        if(rx-lx == 1){
            if(lx == 0) return -1;
            return lx;
        }

        int mid = (lx+rx) >> 1;

        int res = find_first(2*x+1,lx,mid,v);
        if(res == -1){
            res = find_first(2*x+2,mid,rx,v);
        }

        return res;
    }

    int find_first(int v){
        // returns the first occ of v
        return find_first(0,0,siz,v);
    }

    int find_last(int x, int lx, int rx, int v){
        propagate(x,lx,rx);
        if(tr[x].mn > v) return -1;
        if(tr[x].mx < v) return -1;
        if(rx-lx == 1) return lx;

        int mid = (lx+rx) >> 1;

        int res = find_last(2*x+2,mid,rx,v);
        if(res == -1){
            res = find_last(2*x+1,lx,mid,v);            
        }

        return res;
    }

    int find_last(int v){
        // returns the last occ of v
        return find_last(0,0,siz,v);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<pll> a(n);
    rep(i,n) cin >> a[i].ff >> a[i].ss;

    sort(all(a));

    // maintain the counts with a lazy segtree
    // at any point of time, we will ensure that the values in the lazy segtree are non-increasing
    lazysegtree<ll> st(N);
    st.build(N);

    rep(i,n){
        auto [h,k] = a[i];
        ll v = st.query(h-k+1,h-k+1).mn;

        ll first = st.find_first(v);
        ll last = st.find_last(v);
        amin(last,h);

        // debug(h);
        // debug(k);
        // debug(v);
        // debug(first);
        // debug(last);
        st.rupd(last+1,h,1);
            
        ll done = h-last;
        ll more = k-done;
        st.rupd(first,first+more-1,1);

        // rep1(p,5){
        //     ll x = st.query(p,p).mn;
        //     cout << x << " ";
        // }

        // cout << endl << endl;
    }

    ll ans = 0;

    rep(i,N){
        ll c = st.query(i,i).mn;
        ans += c*(c-1)/2;
    }

    cout << ans << endl;

    /*

    rep(i,n){
        auto [h,k] = a[i];
        vector<pll> v;
        rep1(j,h){
            v.pb({cnt[j],j});
        }

        sort(all(v));
        rep(j,k){
            auto [c,pos] = v[j];
            cnt[pos]++;
        }
    }

    ll ans = 0;

    rep(i,N){
        ll c = cnt[i];
        ans += c*(c-1)/2;
    }

    cout << ans << endl;

    */
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• 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