oj.uz

답안 #253338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253338 2020-07-27T18:31:46 Z mode149256 Sails (IOI07_sails) C++14
0 / 100
 95 ms 3832 KB 
/*input
6
3 2
5 3
4 1
2 1
4 3
3 2

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);
    // vl kiek(MX, 0);
    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 - pir + 1, k);

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

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

        // printf("po %lld\n", i);
        // for (int i = 1; i <= 10; ++i)
        // {
        //     printf("%d ", kiek.get(i));
        // }
        // printf("\n");
    }

    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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 1280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 1920 KB Output isn't correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 2516 KB Output isn't correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 3200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 3628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -