oj.uz

Submission #887542

# Submission time Handle Problem Language Result Execution time Memory
887542 2023-12-14T17:42:37 Z Macker Sails (IOI07_sails) C++17
25 / 100
 55 ms 2356 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 = 8;

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 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 2356 KB Output isn't correct
2 Halted 0 ms 0 KB -