oj.uz

Submission #954685

# Submission time Handle Problem Language Result Execution time Memory
954685 2024-03-28T10:50:15 Z codefox Pairs (IOI07_pairs) C++14
100 / 100
 3727 ms 338188 KB 
#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define pipii pair<int, pii>
#define ll long long
#define arr array<int, 2>

#pragma GCC optimize("O2")

int N = 1<<18;
int M = 1<<17;
int K = 17;

int go(int a, int b, int d, vector<vector<arr>> &bin, vector<int> &counter, vector<vector<int>> &upd)
{
    if (bin[a][b][d]==-1)
    {
        upd[a].push_back(0);
        bin[a].push_back({-1, -1});
        bin[a][b][d] = counter[a];
        counter[a]++;
    }
    return bin[a][b][d];
}

void update(int a, int b, vector<vector<arr>> &bin, vector<int> &counter, vector<vector<int>> &upd)
{
    a += N; 
    while (a)
    {
        int curr = 0;
        int bb = b;
        for (int i = K; i >= 0; i--)
        {
            upd[a][curr]++;
            if (bb>=(1<<i))
            {
                bb -= 1<<i;
                curr = go(a, curr, 1, bin, counter, upd);
            }
            else curr = go(a, curr, 0, bin, counter, upd);
        }
        upd[a][curr]++;
        a/=2;
    }
}

ll ac2d(int a, int curr, int l, int r, int x, int y, vector<vector<arr>> &bin, vector<vector<int>> &upd)
{
    if (r <=x || l >= y) return 0;
    if (l >= x && r <= y)
    {
        return upd[a][curr];
    }
    int m = (l+r)/2;
    ll sol = 0;
    if (bin[a][curr][0]!=-1) sol += ac2d(a, bin[a][curr][0], l, m, x, y, bin, upd);
    if (bin[a][curr][1]!=-1) sol += ac2d(a, bin[a][curr][1], m, r, x, y, bin, upd);
    return sol;
}

ll acc(int curr, int l, int r, int a, int b, int x, int y, vector<vector<arr>> &bin, vector<vector<int>> &upd)
{
    if (r <=a || l >= b) return 0;
    if (l >= a && r <= b)
    {
        return ac2d(curr, 0, 0, N, x, y, bin, upd);
    }
    int m = (l+r)/2;
    return acc(curr*2, l, m, a, b, x, y, bin, upd)+ acc(curr*2+1, m, r, a, b, x, y, bin, upd);
}

void update3(int a, int b, vector<vector<int>> &bin)
{
    a += N; 
    while (a)
    {
        int bb = b+N;
        while (bb)
        {
            bin[a][bb]++;
            bb/=2;
        }
        a/=2;
    }
}

ll ac2d3(int a, int curr, int l, int r, int x, int y, vector<vector<int>> &bin)
{
    if (r <=x || l >= y) return 0;
    if (l >= x && r <= y)
    {
        return bin[a][curr];
    }
    int m = (l+r)/2;
    return ac2d3(a, curr*2, l, m, x, y, bin) +
    ac2d3(a, curr*2+1, m, r, x, y, bin);
}

ll acc3(int curr, int l, int r, int a, int b, int x, int y, vector<vector<int>> &bin)
{
    if (r <=a || l >= b) return 0;
    if (l >= a && r <= b)
    {
        return ac2d3(curr, 1, 0, N, x, y, bin);
    }
    int m = (l+r)/2;
    return acc3(curr*2, l, m, a, b, x, y, bin)+ acc3(curr*2+1, m, r, a, b, x, y, bin);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int b, n, d, m;
    cin >> b >> n >> d >> m;

    if (b == 1)
    {
        vector<int> nums(n);
        for (int i =0; i < n; i++) cin >> nums[i];
        sort(nums.begin(), nums.end());

        ll sol = 0;
        queue<int> q;
        for (int i = 0; i < n; i++)
        {
            while (q.size() && nums[i]-q.front()> d) q.pop();
            sol += q.size();
            q.push(nums[i]);
        }
        cout << sol;
    }
    else if (b==2)
    {
        vector<vector<arr>> bin;
        vector<int> counter;
        vector<vector<int>> upd;
        bin.assign(2*N, vector<arr>(1, {-1, -1}));
        counter.assign(2*N, 1);
        upd.assign(2*N, vector<int>(1, 0));

        ll sol = 0;

        for (int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            sol += acc(1, 0, N, x+y-d, x+y+d+1, y-x+M-d, y-x+M+d+1, bin, upd);
            update(x+y, y-x+M, bin, counter, upd);
        }
        cout << sol;
    }
    else if (b==3)
    {
        N = 1<<8;
        M = 1<<7;
        K = 7;

        vector<vector<vector<int>>> bin(76, vector<vector<int>>(2*N, vector<int>(2*N, 0)));

        vector<pipii> coord(n);
        for (int i = 0; i < n; i++)
        {
            int x, y, z;
            cin >> x >> y >> z;
            coord[i] = {z, {x, y}};
        }
        sort(coord.begin(), coord.end());

        ll sol = 0;
        for (int i =0; i < n; i++)
        {
            int x, y, z;
            z = coord[i].first;
            x = coord[i].second.first;
            y = coord[i].second.second;
            for (int j = 0; j <= z; j++)
            {
                int h = d-(z-j);
                if (h <0) continue;
                sol +=acc3(1, 0, N, x+y-h, x+y+h+1, y-x+M-h, y-x+M+h+1, bin[j]);
            }
            update3(x+y, y-x+M, bin[z]);
        }
        cout << sol;
    }

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 860 KB Output is correct
2 Correct 11 ms 1120 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 14 ms 1116 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 14 ms 860 KB Output is correct
3 Correct 14 ms 860 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 65188 KB Output is correct
2 Correct 66 ms 65108 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 61452 KB Output is correct
2 Correct 251 ms 61388 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 97720 KB Output is correct
2 Correct 696 ms 97836 KB Output is correct
3 Correct 515 ms 80996 KB Output is correct
4 Correct 567 ms 90708 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2296 ms 338124 KB Output is correct
2 Correct 2152 ms 338188 KB Output is correct
3 Correct 613 ms 102272 KB Output is correct
4 Correct 617 ms 93044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 80988 KB Output is correct
2 Correct 40 ms 80724 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 82040 KB Output is correct
2 Correct 243 ms 82012 KB Output is correct
3 Correct 201 ms 82008 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 82256 KB Output is correct
2 Correct 2198 ms 82012 KB Output is correct
3 Correct 1006 ms 82768 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1715 ms 82008 KB Output is correct
2 Correct 3727 ms 82260 KB Output is correct
3 Correct 1556 ms 82928 KB Output is correct