oj.uz

Submission #887543

# Submission time Handle Problem Language Result Execution time Memory
887543 2023-12-14T17:44:23 Z Macker Sails (IOI07_sails) C++17
100 / 100
 201 ms 10460 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8540 KB Output is correct
2 Correct 22 ms 8652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8536 KB Output is correct
2 Correct 20 ms 8792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8536 KB Output is correct
2 Correct 20 ms 8540 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8540 KB Output is correct
2 Correct 20 ms 8536 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8536 KB Output is correct
2 Correct 22 ms 8540 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8688 KB Output is correct
2 Correct 63 ms 9048 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 8796 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9036 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 9224 KB Output is correct
2 Correct 135 ms 10064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 9308 KB Output is correct
2 Correct 111 ms 9820 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 9308 KB Output is correct
2 Correct 148 ms 10460 KB Output is correct