제출 #483913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483913		blue	Pairs (IOI07_pairs)	C++17	30 / 100	4099 ms	1936 KiB

pairs

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve_1()
{
    int N, D, M;
    cin >> N >> D >> M;

    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    long long ans = 0;

    int j = 0;
    for(int i = 0; i < N; i++)
    {
        while(j+1 < N && A[j+1] - A[i] <= D)
            j++;

        ans += (j-i);
    }

    cout << ans << '\n';
}

void solve_2()
{
    ;
}

void solve_3()
{
    int N, D, M;
    cin >> N >> D >> M;

    long long ans = 0;

    vector<int> values[1+M][1+M];
    for(int i = 0; i < N; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        values[a][b].push_back(c);
    }

    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= M; j++)
            sort(values[i][j].begin(), values[i][j].end());

    long long res = 0;
    for(int i = 1; i <= M; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            if(values[i][j].empty()) continue;
            for(int i2 = i; i2 <= M; i2++)
            {
                for(int j2 = 1; j2 <= M; j2++)
                {
                    if(i == i2 && j2 <= j) continue;

                    if(values[i2][j2].empty()) continue;

                    int basicDist = abs(i-i2) + abs(j-j2);

                    // cerr << "A\n";
                    int q = 0;
                    int r = 0;
                    for(int p = 0; p < int(values[i][j].size()); p++)
                    {
                        // cerr << "check C\n";
                        while((r+1) < int(values[i2][j2].size()) && basicDist + values[i2][j2][r+1] - values[i][j][p] <= D)
                            r++;
                        // cerr << "check D\n";
                        while(q < int(values[i2][j2].size()) && basicDist + values[i][j][p] - values[i2][j2][q] > D)
                            q++;
                        // cerr << "check E\n";

                        // cerr << i2 << ' ' << j2 << ' ' << values[i2][j2][r] << ' ' << values[i2][j2][q] << '\n';
                        //
                        // cerr << i << ' ' << j << ' ' << values[i][j][p] << " : "  << max(0, q-r+1) << '\n';
                        // cerr << "\n\n\n";
                        if(basicDist + values[i][j][p] - values[i2][j2][q] <= D)
                            if(basicDist + values[i2][j2][r] - values[i][j][p] <= D)
                                if(values[i][j][p] >= values[i2][j2][q])
                                    if(values[i2][j2][r] >= values[i][j][p])
                                        res += max(0, q-r+1);
                    }
                    // cerr << "B\n";

                }
            }

            int q = 0;
            for(int p = 0; p < int(values[i][j].size()); p++)
            {
                while((q+1) < int(values[i][j].size()) && values[i][j][q+1] - values[i][j][p] <= D)
                    q++;

                res += (q-p);
            }
        }
    }



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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int B;
    cin >> B;

    if(B == 1) solve_1();
    else if(B == 2) solve_2();
    else if(B == 3) solve_3();
}

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp: In function 'void solve_3()':
pairs.cpp:39:15: warning: unused variable 'ans' [-Wunused-variable]
   39 |     long long ans = 0;
      |               ^~~

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