oj.uz

Submission #483913

# Submission time Handle Problem Language Result Execution time Memory
483913 2021-11-01T10:41:51 Z blue Pairs (IOI07_pairs) C++17
30 / 100
 4000 ms 1936 KB 
#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();
}

Compilation message

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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 716 KB Output is correct
2 Correct 15 ms 588 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 588 KB Output is correct
2 Correct 16 ms 588 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 716 KB Output is correct
2 Correct 18 ms 588 KB Output is correct
3 Correct 15 ms 716 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 1360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2245 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4099 ms 1936 KB Time limit exceeded
2 Halted 0 ms 0 KB -