Submission #253338

#	Time	Username	Problem	Language	Result	Execution time	Memory
253338		mode149256	Sails (IOI07_sails)	C++14	0 / 100	95 ms	3832 KiB

sails

/*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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10