Submission #1097126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097126		Whisper	Sails (IOI07_sails)	C++17	100 / 100	121 ms	8276 KiB

sails

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                         100005
int nArr;
struct Sail{
    int height, flag;
    Sail(){}
    Sail(int _height, int _flag): height(_height), flag(_flag){}

    bool operator < (const Sail& o) const{
        return height < o.height;
    }
} A[MAX];
struct SegmentTree{
    vector<int> st, lz;
    int n;
    SegmentTree(int _n = 0){
        this -> n = _n;
        st.resize((n << 2) + 5);
        lz.resize((n << 2) + 5);
    }
    #define lson                (nd << 1)
    #define rson                (nd << 1 | 1)

    void pushDown(int nd){
        if(!lz[nd]) return;

        st[lson] += lz[nd];
        st[rson] += lz[nd];

        lz[lson] += lz[nd];
        lz[rson] += lz[nd];

        lz[nd] = 0;
    }
    void upd(int nd, int l, int r, int u, int v, int value){
        if (u > r || v < l) return;
        if (u <= l && v >= r) {
            st[nd] += value;
            lz[nd] += value;
            return;
        }
        pushDown(nd);
        int m = (l + r) >> 1;
        upd(lson, l, m, u, v, value);
        upd(rson, m + 1, r, u, v, value);
        st[nd] = max(st[lson], st[rson]);
    }

    int query(int nd, int l, int r, int u, int v){
        if (u > r || v < l) return 0;
        if (u <= l && v >= r) return st[nd];
        int m = (l + r) >> 1;

        pushDown(nd);
        int ql = query(lson, l, m, u, v);
        int qr = query(rson, m + 1, r, u, v);
        return max(ql, qr);
    }

    int findLeft(int value, int nd, int l, int r){
        if(st[1] <= value) return 1;
        if (l == r){
            return l + 1;
        }
        int m = (l + r) >> 1;
        pushDown(nd);
        if(st[rson] > value){
            return findLeft(value, rson, m + 1, r);
        }
        return findLeft(value, lson, l, m);
    }
    int findRight(int value, int nd, int l, int r){
        if (l == r){
            return l;
        }
        int m = (l + r) >> 1;
        pushDown(nd);
        if(st[rson] >= value){
            return findRight(value, rson, m + 1, r);
        }
        return findRight(value, lson, l, m);
    }

    int findLeft(int value){
        return findLeft(value, 1, 1, n);
    }
    int findRight(int value){
        return findRight(value, 1, 1, n);
    }
    void upd(int l, int r, int v){
        upd(1, 1, n, l, r, v);
    }
    int query(int l, int r){
        return query(1, 1, n, l, r);
    }
};

void process(void){
    cin >> nArr;
    int lim = 0;
    for (int i = 1; i <= nArr; ++i){
        cin >> A[i].height >> A[i].flag;
        maximize(lim, A[i].height);
    }
    sort(A + 1, A + nArr + 1);
    SegmentTree myit(lim + 5);

    for (int i = 1; i <= nArr; ++i){
        int value = myit.query(A[i].height - A[i].flag + 1, A[i].height - A[i].flag + 1);
        int L = myit.findLeft(value);
        int R = myit.findRight(value);
        if(R > lim){
            myit.upd(L, min(lim, L + A[i].flag - 1), 1);
        }
        else{
            myit.upd(R + 1, A[i].height, 1);
            myit.upd(L, L + A[i].flag - A[i].height + R - 1, 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= lim; ++i){
        int value = myit.query(i, i);
        ans += value * (value - 1) / 2;
    }
    cout << ans;
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 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