oj.uz

답안 #253343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253343 2020-07-27T18:36:13 Z mode149256 Sails (IOI07_sails) C++14
100 / 100
 102 ms 3824 KB 
/*input
5
1 1
2 1
3 2
4 3
5 4

13
3 3
3 3
5 1
4 1
5 1
6 1
6 1
6 1
3 3
3 3
3 3
3 3
3 3
*/
#include <bits/stdc++.h>
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) {
    return pair<T, T>(a.x + b.x, a.y + b.y);
}
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) {
    return pair<T, T>(a.x - b.x, a.y - b.y);
}
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) {
    return (a.x * b.x + a.y * b.y);
}
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) {
    return (a.x * b.y - a.y * b.x);
}

template<typename T>
void print(vector<T> vec, string name = "") {
    cout << name;

    for (auto u : vec) {
        cout << u << ' ';
    }

    cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;

ll add(ll a) {
    return a * (a - 1) / 2;
}

struct FENWICK {
    vl A;
    int N;
    FENWICK(int n): N(n) {
        A.resize(n + 1, 0);
    }
    void add(ll i, ll x) {
        for (; i <= N; i += (i) & (-i))
            A[i] += x;
    }
    ll get(ll i) {
        ll get = 0;
        for (; i > 0; i -= (i) & (-i))
            get += A[i];
        return get;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;

    FENWICK kiek(MX);
    ll ats = 0;
    vpl sk(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> sk[i].x >> sk[i].y;
    }

    sort(sk.begin(), sk.end());

    auto findFir = [&](ll j) {
        ll dab = kiek.get(j);
        ll l = 1;
        ll h = j;

        while (l < h) {
            ll m = (l + h) / 2;
            if (kiek.get(m) == dab)
                h = m;
            else
                l = m + 1;
        }
        return l;
    };

    auto findSec = [&](ll j) {
        ll dab = kiek.get(j);
        ll l = j;
        ll h = MX;

        while (l < h) {
            ll m = (l + h + 1) / 2;
            if (kiek.get(m) == dab)
                l = m;
            else
                h = m - 1;
        }
        return l;
    };

    for (ll i = 0; i < N; ++i)
    {
        ll h = sk[i].x;
        ll k = sk[i].y;

        ll pir = findFir(h - k + 1);
        ll ant = findSec(h - k + 1);

        ll ilgis = min(ant - (h - k + 1) + 1, k);

        kiek.add(pir, 1);
        kiek.add(pir + ilgis, -1);

        kiek.add(ant + 1, 1);
        kiek.add(ant + 1 + (k - ilgis), -1);
    }

    for (int i = 1; i <= MX; ++i)
    {
        ats += add(kiek.get(i));
    }
    printf("%lld\n", ats);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1280 KB Output is correct
2 Correct 24 ms 1920 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1664 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1920 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 2304 KB Output is correct
2 Correct 68 ms 3200 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 2560 KB Output is correct
2 Correct 66 ms 3292 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 2748 KB Output is correct
2 Correct 65 ms 3824 KB Output is correct