Submission #383735

#	Time	Username	Problem	Language	Result	Execution time	Memory
383735		JerryLiu06	Pairs (IOI07_pairs)	C++11	100 / 100	477 ms	111204 KiB

pairs

#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 (stderr)

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 / 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