oj.uz

Submission #383735

# Submission time Handle Problem Language Result Execution time Memory
383735 2021-03-30T18:36:26 Z JerryLiu06 Pairs (IOI07_pairs) C++11
100 / 100
 477 ms 111204 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

typedef long long ll;

#define pb push_back

#define f first
#define s second

int B, N, D, M;

ll solve1() {
    vector<int> A; for (int i = 0; i < N; i++) { int X; cin >> X; A.pb(X); }

    sort(A.begin(), A.end()); int L = 0; int R = 0; ll res = 0;
    
    for (int L = 0; L < N; L++) { while (R < N && A[R] - A[L] <= D) R++; res += R - L - 1; } return res;
}
const int MX = 150000; ll tree1[MX + 10];

void update(int ind, ll val) {
    while (ind <= MX) { tree1[ind] += val; ind += (ind & (-ind));}
}
ll query(int ind) {
    ll sum = 0; while (ind > 0) { sum += tree1[ind]; ind -= (ind & (-ind)); } return sum;
}
ll solve2() {
    vector<pii> A; for (int i = 0; i < N; i++) { int X, Y; cin >> X >> Y; A.pb(pii {X - Y, X + Y}); }

    sort(A.begin(), A.end()); memset(tree1, 0, sizeof tree1); int R = 0; ll res = 0;
    
    for (int L = 0; L < N; L++) {
        
        while (R < N && A[R].f - A[L].f <= D) { 
            res += (query(min(MX, A[R].s + D)) - query(A[R].s - D - 1)); update(A[R++].s, 1); 
        }
        update(A[L].s, -1);
    }
    return res;
}
const int MMX = 75; const int NMX = 230; ll tree2[NMX + 10][NMX + 10][NMX + 10];

void update(int x, int y, int z, ll val) {
    for (int i = x; i <= NMX; i += (i & -i)) for (int j = y; j <= NMX; j += (j & -j)) {
        for (int k = z; k <= NMX; k += (k & -k)) tree2[i][j][k] += val;
    }
}
ll query(int x, int y, int z) {
    ll sum = 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)) sum += tree2[i][j][k];
    }
    return sum;
}
ll solve3() {
    vector<ppp> A; for (int i = 0; i < N; i++) { int X, Y, Z; cin >> X >> Y >> Z;
        int T1 = X + Y + Z; int T2 = X + Y - Z + MMX; int T3 = X - Y + Z + MMX; int T4 = X - Y - Z + 2 * MMX;

        A.pb(ppp {{T1, T2}, {T3, T4}});
    }
    sort(A.begin(), A.end()); memset(tree2, 0, sizeof tree2); int R = 0; ll res = 0;

    for (int L = 0; L < N; L++) {

        while (R < N && A[R].f.f - A[L].f.f <= D) { 
            int X1 = min(A[R].f.s + D, NMX); int Y1 = A[R].f.s - D - 1;
            int X2 = min(A[R].s.f + D, NMX); int Y2 = A[R].s.f - D - 1;
            int X3 = min(A[R].s.s + D, NMX); int Y3 = A[R].s.s - D - 1;

            res += query(X1, X2, X3); res -= (query(Y1, X2, X3) + query(X1, Y2, X3) + query(X1, X2, Y3));
            res += (query(X1, Y2, Y3) + query(Y1, X2, Y3) + query(Y1, Y2, X3)); res -= query(Y1, Y2, Y3);
            
            update(A[R].f.s, A[R].s.f, A[R].s.s, 1); R++;
        }
        update(A[L].f.s, A[L].s.f, A[L].s.s, -1);
    }
    return res;
}

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

    cin >> B >> N >> D >> M;
    
    if (B == 1) cout << solve1(); else if (B == 2) cout << solve2(); else cout << solve3();
}

Compilation message

pairs.cpp: In function 'll solve1()':
pairs.cpp:20:35: warning: unused variable 'L' [-Wunused-variable]
   20 |     sort(A.begin(), A.end()); int L = 0; int R = 0; ll res = 0;
      |                                   ^

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1776 KB Output is correct
2 Correct 20 ms 1776 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1724 KB Output is correct
2 Correct 21 ms 1796 KB Output is correct
3 Correct 20 ms 1776 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3212 KB Output is correct
2 Correct 35 ms 3048 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3372 KB Output is correct
2 Correct 36 ms 3176 KB Output is correct
3 Correct 36 ms 3316 KB Output is correct
4 Correct 36 ms 3176 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3560 KB Output is correct
2 Correct 38 ms 3580 KB Output is correct
3 Correct 38 ms 3552 KB Output is correct
4 Correct 48 ms 3588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 108652 KB Output is correct
2 Correct 56 ms 108544 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 110912 KB Output is correct
2 Correct 176 ms 110820 KB Output is correct
3 Correct 210 ms 110820 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 111076 KB Output is correct
2 Correct 413 ms 111204 KB Output is correct
3 Correct 179 ms 111076 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 111204 KB Output is correct
2 Correct 460 ms 111092 KB Output is correct
3 Correct 208 ms 111204 KB Output is correct