Submission #887543

#	Time	Username	Problem	Language	Result	Execution time	Memory
887543		Macker	Sails (IOI07_sails)	C++17	100 / 100	201 ms	10460 KiB

sails

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

struct node{
    ll min = 0, max = 0, val = 0, lz = 0;
};
vector<node> st;
int len = 131072;

void prop(int i, int ln){
    node& l = st[i * 2], & r = st[i * 2 + 1]; ll& val = st[i].lz;
    l.lz += val; l.max += val; l.min += val;
    l.val += ln / 2 * val;
    r.lz += val; r.max += val; r.min += val;
    r.val += ln / 2 * val;
    val = 0;
}

ll getv(int k, int i = 1, int s = 0, int e = len){
    if(k < s || k >= e) return 0;
    if(k == s && s + 1 == e) return st[i].val;
    prop(i, (e - s));
    return getv(k, i * 2, s, (s + e) / 2) + getv(k, i * 2 + 1, (s + e) / 2, e);
}

int biggerv(int v, int i = 1, int s = 0, int e = len){
    if(s + 1 == e) return s;
    prop(i, (e - s));
    if(st[i * 2 + 1].min <= v) return biggerv(v, i * 2 + 1, (s + e) / 2, e);
    else return biggerv(v, i * 2, s, (s + e) / 2);
}

int smallerv(int v, int i = 1, int s = 0, int e = len){
    if(s + 1 == e) return s;
    prop(i, (e - s));
    if(st[i * 2 + 1].min < v) return smallerv(v, i * 2 + 1, (s + e) / 2, e);
    else return smallerv(v, i * 2, s, (s + e) / 2);
}

void add(int l, int r, ll val, int i = 1, int s = 0, int e = len){
    if(l >= e || s >= r) return;
    if(l <= s && e <= r){
        st[i].val += (e - s) * val;
        st[i].min += val;
        st[i].max += val;
        st[i].lz += val;
        return;
    }
    prop(i, (e - s));
    add(l, r, val, i * 2, s, (s + e) / 2);
    add(l, r, val, i * 2 + 1, (s + e) / 2, e);
    st[i].val = st[i * 2].val + st[i * 2 + 1].val;
    st[i].max = max(st[i * 2].max, st[i * 2 + 1].max);
    st[i].min = min(st[i * 2].min, st[i * 2 + 1].min);
}

int main()
{
    int n; cin >> n;
    st.resize(2*len, node());
    vector<pair<int, int>> v(n);
    for (auto &i : v) cin >> i.first >> i.second;

    sort(all(v));
    for (auto i : v) {
        int s = len - i.first, k = i.second;
        ll val = getv(s + k - 1);
        int es = smallerv(val);
        if(es >= s)
            add(s, es + 1, 1);
        int d = min(k - (es - s + 1), k);
        int eb = biggerv(val);
        if(d > 0)
            add(eb - d + 1, eb + 1, 1);
        //for (int j = 0; j < len; j++) cout << getv(j) << " ";
        //cout << endl;
        //cout << endl;
    }
    
    ll res = 0;
    for (int i = 0; i < len; i++) {
        ll c = getv(i);
        res += c * (c - 1) / 2;
    }
    cout << res << endl;
}

• 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