Submission #1279566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279566		quangminh412	Pairs (IOI07_pairs)	C++17	100 / 100	184 ms	48604 KiB

pairs

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
struct FenwickTree
{
    vector<int> bits;
    int n;

    FenwickTree(int n) : n(n) { bits.resize(n + 1, 0); }

    void update(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
            bits[pos] += val;
    }

    int query(int pos)
    {
        int res = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
            res += bits[pos];
        return res;
    }
    int query(int l, int r) { return query(r) - query(l - 1); }
};

struct FenwickTree3D
{
    vector<vector<vector<int>>> bits;
    int n;

    FenwickTree3D(int n) : n(n)
    {
        bits.resize(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    }

    void update(int x, int y, int z, int val)
    {
        for (int i = x; i <= n; i += (i & (-i)))
            for (int j = y; j <= n; j += (j & (-j)))
                for (int k = z; k <= n; k += (k & (-k)))
                    bits[i][j][k] += val;
    }

    int sum(int x, int y, int z)
    {
        int res = 0;
        for (int i = x; i > 0; i -= (i & (-i)))
            for (int j = y; j > 0; j -= (j & (-j)))
                for (int k = z; k > 0; k -= (k & (-k)))
                    res += bits[i][j][k];
        return res;
    }

    int query(int x1, int y1, int z1, int x2, int y2, int z2)
    {
        return sum(x2, y2, z2) - (sum(x1 - 1, y2, z2) + sum(x2, y1 - 1, z2) + sum(x2, y2, z1 - 1))
        + sum(x1 - 1, y1 - 1, z2) + sum(x2, y1 - 1, z1 - 1) + sum(x1 - 1, y2, z1 - 1) - sum(x1 - 1, y1 - 1, z1 - 1);
    }
};

int b, n, d, m;

void solve1()
{
    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    sort(a.begin(), a.end());
    int j = 0;
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        while (a[i] - a[j] > d)
            j++;
        res += i - j;
    }

    cout << res << '\n';
}

bool cmp2(pair<int, int>& a, pair<int, int>& b)
{
    return a.first + a.second < b.first + b.second;
}
void solve2()
{
    vector<pair<int, int>> a(n);
    for (pair<int, int>& it : a)
        cin >> it.first >> it.second;
    sort(a.begin(), a.end(), cmp2);

    int lim = 75e3, cursor = 0;
    FenwickTree bit(2 * lim);
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        int S = a[i].first + a[i].second, T = a[i].first - a[i].second;
        while (1)
        {
            int prevS = a[cursor].first + a[cursor].second, prevT = a[cursor].first - a[cursor].second;
            if (S - prevS > d)
            {
                bit.update(prevT + lim, -1);
                cursor++;
            } else
                break;
        }
        int L = max(1, T - d + lim), R = min(2 * lim, T + d + lim);
        res += bit.query(L, R);
        bit.update(T + lim, 1);
    }

    cout << res << '\n';
}

bool cmp3(array<int, 3>& a, array<int, 3>& b)
{
    return a[0] + a[1] + a[2] < b[0] + b[1] + b[2];
}
void solve3()
{
    vector<array<int, 3>> a(n);
    for (array<int, 3> &it : a)
        cin >> it[0] >> it[1] >> it[2];
    sort(a.begin(), a.end(), cmp3);
    int lim = 75, cursor = 0;
    FenwickTree3D bit(3 * lim);
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        int S = a[i][0] + a[i][1] + a[i][2], T = -a[i][0] + a[i][1] + a[i][2], U = a[i][0] - a[i][1] + a[i][2], V = a[i][0] + a[i][1] - a[i][2];
        while (1)
        {
            int prevS = a[cursor][0] + a[cursor][1] + a[cursor][2], prevT = -a[cursor][0] + a[cursor][1] + a[cursor][2];
            int prevU = a[cursor][0] - a[cursor][1] + a[cursor][2], prevV = a[cursor][0] + a[cursor][1] - a[cursor][2];
            if (S - prevS > d)
            {
                bit.update(prevT + lim, prevU + lim, prevV + lim, -1);
                cursor++;
            } else
                break;
        }
        int lT = max(1, T - d + lim), rT = min(3 * lim, T + d + lim);
        int lU = max(1, U - d + lim), rU = min(3 * lim, U + d + lim);
        int lV = max(1, V - d + lim), rV = min(3 * lim, V + d + lim);
        res += bit.query(lT, lU, lV, rT, rU, rV);
        bit.update(T + lim, U + lim, V + lim, 1);
    }
    cout << res << '\n';
}

void solve()
{
    cin >> b >> n >> d >> m;

    if (b == 1)
        solve1();
    else
    if (b == 2)
        solve2();
    else
        solve3();
}

Compilation message (stderr)

pairs.cpp: In function 'int main()':
pairs.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10