Submission #1033936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033936		daoda	Sails (IOI07_sails)	C++17	100 / 100	60 ms	3156 KiB

sails

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

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(ll x=a;x < ll(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;

// template <class T>
// using Tree = 
    // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = ll(1e9) + 10;
const ll INIT = 7;
const ll MAX_VAL = 50;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 20;
const ll MAX_M = MAX_N;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;

vi rd = {0, 1, 0, -1}, cd = {1, 0, -1, 0};

ll add(ll a, ll b) {
    return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}

ll mult(ll a, ll b) {
    return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

const int MAX_H = 1e5;

struct BIT {
    vll tree;
    int sz;

    BIT(int inp_sz) { sz = inp_sz; tree.resize(sz + 1, 0); }

    void add(int ind, ll val) {
        while(ind <= sz) {  
            tree[ind] += val;
            ind += ind & -ind;
        }
    }   

    ll pref_sum(int ind) {
        ll sum = 0;

        while(ind >= 1) {
            sum += tree[ind];
            ind -= ind & -ind;
        }

        return sum;
    }

    ll sum(int a, int b) {
        return pref_sum(b) - pref_sum(a - 1);
    }

    void set(int ind, ll val) {
        add(ind, val - sum(ind, ind));
    }

    void addrange(int l, int r, ll val) {
        if(l > r) return;

        add(l, val);
        if(r < sz) add(r + 1, -val);
    }
};

int main() { 

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    fast

    // TESTCASE {
        
    // }   
    
    int n;
    cin >> n;

    vpi inp(n);

    FOR(i, 0, n) {
        cin >> inp[i].first >> inp[i].second;
        // inp[i].first = i + 1;
        // inp[i].second = min(inp[i].first, 3);
    }

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

    BIT bit1(MAX_H);

    FOR(i, 0, n) {
        int height = inp[i].first, sails = inp[i].second;

        int last_val = bit1.pref_sum(height - sails + 1);

        // cout << lb << " " << upb << endl;

        int lb = height - sails + 1, upb = height + 1;

        while(lb < upb) {
            int mid = (upb + lb) / 2;

            if(bit1.pref_sum(mid) != last_val) upb = mid;
            else lb = mid + 1;

            // cout << lb << " " << upb << endl;
        }

        bit1.addrange(upb, height, 1);

        int lb2 = 1, upb2 = height - sails + 1;

        while(lb2 < upb2) {
            int mid = (lb2 + upb2) / 2;

            if(bit1.pref_sum(mid) == last_val) upb2 = mid;
            else lb2 = mid + 1;
        }

        int unupdated = sails - (height - upb + 1);

        bit1.addrange(upb2, upb2 + unupdated - 1, 1);

        // FOR(j, 1, 20) cout << bit1.pref_sum(j) << " ";
        // cout << endl;
    }

    ll ans = 0;

    FOR(i, 1, MAX_H + 1) {
        // cout << bit1.pref_sum(i) << " ";

        ll cur_val = max(bit1.pref_sum(i) - 1, 0ll);
        ans += (cur_val * (cur_val + 1)) / 2ll;
    }
    // cout << endl;

    cout << ans;
}

• 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