oj.uz

Submission #1063505

# Submission time Handle Problem Language Result Execution time Memory
1063505 2024-08-17T19:39:42 Z orcslop Sails (IOI07_sails) C++17
100 / 100
 135 ms 4188 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>

template <class T> class BIT {
  private:
    int n;
    vector<T> bit;
    vector<T> arr;

  public:
    BIT(int n) : n(n), bit(n + 1), arr(n) {}

    void set(int k, T val) { add(k, val - arr[k]); }

    void add(int k, T val) {
        arr[k] += val;
        k++;
        for (; k <= n; k += k & -k) { bit[k] += val; }
    }

    T query(int a, int b) {
        b++;
        T s = 0;
        for (; a > 0; a -= a & -a) { s -= bit[a]; }
        for (; b > 0; b -= b & -b) { s += bit[b]; }
        return s;
    }
};


template <class T> class RURQBIT {
    private : 
        int n; 
        vector<T> a; 
        BIT<T> b, c; 
    public : 
        RURQBIT(int n) : n(n), a(n + 1), b(n + 2), c(n + 2){}

        void build(vector<int> &v){
            for(int i = 1; i <= sz(v); i++){
                a[i] = v[i - 1]; 
                b.set(i, a[i] - a[i - 1]); 
                c.set(i, i * (a[i] - a[i - 1])); 
            }
        }

        void add(int l, int r, T v){
            if(l > r) return; 
            b.add(l, v); 
            b.add(r + 1, -v); 
            c.add(l, l * v); 
            c.add(r + 1, -(r + 1) * v); 
        }

        T query(int l, int r){
            T rs = (r + 1) * b.query(1, r) - c.query(1, r); 
            T ls = l * b.query(1, l - 1) - c.query(1, l - 1); 
            return rs - ls; 
        }

        T query(int l){
            return query(l, l); 
        }
}; 

const int MAXN = 1e5 + 5; 

int n; 
pii v[MAXN]; 
RURQBIT<int> bit(MAXN); 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; 
    for(int i = 0; i < n; i++){
        cin >> v[i].f >> v[i].s; 
        // cout << v[i].f   << ' ' << v[i].s << '\n'; 
    }
    sort(v, v + n); 
    for(int i = 0; i < n; i++){
        int val = bit.query(v[i].f - v[i].s + 1); 
        int lo = 1, hi = v[i].f; 
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (bit.query(mid) >= val) lo = mid; 
            else hi = mid - 1;
        }
        int ub = lo; 
        lo = 1, hi = v[i].f; 
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (bit.query(mid) <= val) hi = mid;
            else lo = mid + 1;
        }
        int lb = lo; 
        // cout << lb << ' ' << ub << '\n'; 
        bit.add(ub + 1, v[i].f, 1); 
        bit.add(lb, lb + v[i].s - v[i].f + ub - 1, 1); 
    }
    ll ans = 0; 
    // cout << v[n - 1].f << ' ' << v[n - 1].s << '\n'; 
    for(int i = 1; i <= v[n - 1].f; i++){
        ll curr = bit.query(i); 
        ans += curr * (curr - 1) / 2; 
    }
    cout << ans << '\n'; 
    return 0; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2436 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2908 KB Output is correct
2 Correct 4 ms 2460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2396 KB Output is correct
2 Correct 24 ms 2888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3332 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3776 KB Output is correct
2 Correct 100 ms 3928 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4104 KB Output is correct
2 Correct 91 ms 3672 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 4184 KB Output is correct
2 Correct 82 ms 4188 KB Output is correct