Submission #1147138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147138		RedGrey1993	Sails (IOI07_sails)	C++20	100 / 100	889 ms	7752 KiB

sails

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

// 函数名后面加 ll 就可以计算 long long类型对应的结果
// __builtin_ffs(x)  // 返回x中最后一个为1的位是从后向前的第几位
// __builtin_popcount(x)  // x中1的个数
// __builtin_ctz(x)  // x末尾0的个数。x=0时结果未定义。
// __builtin_clz(x)  // x前导0的个数。x=0时结果未定义。
// __builtin_parity(x)  // x中1的奇偶性。
#define highest_bit1_index(x) (31 - __builtin_clz(x))
#define highest_bit1_index_ll(x) (63 - __builtin_clzll(x))
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif


template <typename T>
struct Node {
    struct _LazyTag {
        static constexpr T NOT_SET = numeric_limits<T>::lowest();
        T additional_val_every_item = 0;
        T set_val_every_item = NOT_SET;
        void Reset() {
            additional_val_every_item = 0;
            set_val_every_item = NOT_SET;
        }
    };
    Node() : sum(0), min(numeric_limits<T>::max()), max(numeric_limits<T>::min()) {}
    Node(const T& v) : sum(v), min(v), max(v) {}
    T sum = 0, min = 0, max = 0;
    int min_idx = 0;
    _LazyTag lazy_tag;
    int left, right;  // [left, right)
};
template <typename T>
using LazyTag = typename Node<T>::_LazyTag;

template<typename T>
class SegmentTree3 {
public:
    SegmentTree3(unsigned int size) {
        this->size = size;
        data.resize(size << 1);
        A.resize(size, 0);
    }
    void Resize(unsigned int size) {
        this->size = size;
        if (size == A.size())
            return;
        data.resize(size << 1);
        A.resize(size, 0);
    }
    void Init() { Init(0, 0, size); }
    // 将[a,b)范围内所有的值，作对应的更新操作
    void Update(int a, int b, const LazyTag<T>& tag) { Update(a, b, tag, 0); }
    // 查询[a,b)范围的目标值
    Node<T> Query(int a, int b) { return Query(a, b, 0); }

    vector<T> A;

// private:
    // 根据不同的情况实现Apply和Combine
    void Apply(const LazyTag<T>& tag, int k) {
        if (tag.set_val_every_item != LazyTag<T>::NOT_SET) {
            data[k].lazy_tag.additional_val_every_item = 0;
            data[k].lazy_tag.set_val_every_item = tag.set_val_every_item;
            data[k].sum = (data[k].right - data[k].left) * tag.set_val_every_item;
            data[k].max = data[k].min = tag.set_val_every_item;
            data[k].min_idx = data[k].left;
        }
        if (tag.additional_val_every_item != 0) {
            data[k].lazy_tag.additional_val_every_item += tag.additional_val_every_item;
            data[k].sum += (data[k].right - data[k].left) * tag.additional_val_every_item;
            data[k].max += tag.additional_val_every_item;
            data[k].min += tag.additional_val_every_item;
        }
    }

    // a -> left child, a -> right child
    void Combine(const Node<T>& a, const Node<T>& b, Node<T>& c) {
        c.sum = a.sum + b.sum;
        if (a.min <= b.min) c.min_idx = a.min_idx;
        else c.min_idx = b.min_idx;
        c.min = min(a.min, b.min);
        c.max = max(a.max, b.max);
    }

    // Init [l,r)
    void Init(int k, int l, int r) {
        if (r - l == 1) {  // 叶子节点
            data[k] = Node<T>(A[l]);
            data[k].min_idx = l;
        } else {
            int mid = l + (r - l) / 2;
            int chl = k + 1, chr = k + 2 * (mid - l);
            Init(chl, l, mid);
            Init(chr, mid, r);
            Combine(data[chl], data[chr], data[k]);
        }
        data[k].left = l;
        data[k].right = r;
    }

    void Update(int a, int b, const LazyTag<T>& tag, int k) {
        if (b <= data[k].left || a >= data[k].right)  //没有交集
            return;
        else if (a <= data[k].left && data[k].right <= b) {  //完全包含
            Apply(tag, k);
        } else {  //有交集
            int mid = data[k].left + (data[k].right - data[k].left) / 2;
            int chl = k + 1, chr = k + 2 * (mid - data[k].left);

            PushDown(k, chl, chr);

            Update(a, b, tag, chl);
            Update(a, b, tag, chr);
            
            Combine(data[chl], data[chr], data[k]);
        }
    }

    inline void PushDown(int k, int chl, int chr) {
        if (data[k].right - data[k].left > 1) {
            Apply(data[k].lazy_tag, chl);
            Apply(data[k].lazy_tag, chr);
            data[k].lazy_tag.Reset();
        }
    }

    Node<T> Query(int a, int b, int k) {
        // [a,b) 和 [l,r)完全不相交
        if (data[k].right <= a || b <= data[k].left) {
            return Node<T>();
        }
        // [a,b)完全包含[l,r)，返回当前值
        if (a <= data[k].left && data[k].right <= b) {
            return data[k];
        }

        int mid = data[k].left + (data[k].right - data[k].left) / 2;
        int chl = k + 1, chr = k + 2 * (mid - data[k].left);

        PushDown(k, chl, chr);
        Node<T> c;
        Combine(Query(a, b, chl), Query(a, b, chr), c);

        return c;
    }

    vector<Node<T>> data;
    int size;
};

class Solution {
public:
    void Solve() {
        int n;
        while(cin>>n) {
            vector<pii> masts(n);
            cin>>masts;
            sort(all(masts));
            dbg(masts);

            int max_h = masts.back().first;
            SegmentTree3<int> st(max_h);
            fill(all(st.A), 0);
            st.Init();

            ll ans = 0;
            rep(i,0,n) {
                int h = masts[i].first;
                int k = masts[i].second;
                auto ret = st.Query(h-k, h-k+1);
                
                int l = 0, r = h-k+1;
                while(l < r) {
                    int mid = l + (r-l) / 2;
                    if (st.Query(mid, mid+1).min > ret.min) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                int l1 = l;
                l = h-k, r = h;
                while(l < r) {
                    int mid = l + (r-l) / 2;
                    if (st.Query(mid, mid+1).min >= ret.min) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                int l2 = l;

                LazyTag<int> tag;
                tag.additional_val_every_item = 1;
                st.Update(l2, h, tag);
                st.Update(l1, l1+(k-(h-l2)), tag);
            }

            rep(i,0,max_h) {
                int x = st.Query(i, i+1).min;
                ans += 1ll * x * (x-1) / 2;
            }
            cout << ans << "\n";
        }
        cout.flush();
    }
private:
};

// # define FILE_IO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    set_io("sails/sails");
    Solution().Solve();

    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