Submission #1060605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060605		KasymK	Pairs (IOI07_pairs)	C++17	80 / 100	4046 ms	101460 KiB

pairs

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second	
#define all(v) v.begin(), v.end()
#define int long long
#define pb push_back
#define pii pair<int, int>
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n, d, m, b;

const int N = 75000 << 4;
 
vector<int> st(N << 2), lz(N << 2);
 
void LZ(int nd, int l, int r) {
    st[nd] += lz[nd];
 
    if (l != r) {
        int ch = (nd << 1) + 1;
        lz[ch] += lz[nd];
        lz[ch + 1] += lz[nd];
    }
 
    lz[nd] = 0;
}
 
void upd(int nd, int l, int r, int x, int y, int vl) {
    LZ(nd, l, r);
 
    if (r < x || y < l) return;
 
    if (x <= l && r <= y) {
        lz[nd] += vl;
        LZ(nd, l, r);
 
        return;
    }
 
    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    upd(ch, l, md, x, y, vl); upd(ch + 1, md + 1, r, x, y, vl);
}
 
int fnd(int nd, int l, int r, int x) {
    LZ(nd, l, r);
 
    if (r < x || x < l) return 0;
 
    if (l == r) return st[nd];
 
    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return fnd(ch, l, md, x) + fnd(ch + 1, md + 1, r, x);
}

void f(){
    vector<int> v;
    for(int i = 1; i <= n; ++i){
        int x;
        scanf("%lld", &x);
        v.pb(x);
    }
    sort(all(v));
    int answer = 0;
    for(auto I = v.begin(); I != v.end(); ++I){
        int x = *I;
        auto it = upper_bound(all(v), x-d-1);
        answer += (I-it);
    }
    printf("%lld\n", answer);
}

void f1(){
    int D = d, B = b, M = m;
    D = min(D, M << 2);
    vector<vector<int>> a(n, vector<int>(B));
    for(auto &i : a)
        for(auto &j : i)
            scanf("%lld", &j);
    map<int, vector<pii>> m;
    for (int i = 0; i < n; i++) {
        int x = a[i][0], y = a[i][1];
        a[i][0] = x - y + (M << 1); a[i][1] = x + y + (M << 1);

        m[a[i][1]].pb({a[i][0], 0});
        m[a[i][1] - D].pb({a[i][0], 1});
        m[a[i][1] + D + 1].pb({a[i][0], 2});
    }
    int ans = 0;
    for (auto i : m) {
        for (auto j : i.ss) {
            if (j.ss == 1) upd(0, 0, N - 1, j.ff - D, j.ff + D, 1);
            else if (j.ss == 2) upd(0, 0, N - 1, j.ff - D, j.ff + D, -1);
        }
        for (auto j : i.ss) {
            if (!j.ss) ans += fnd(0, 0, N - 1, j.ff) - 1;
        }
    }
    ans >>= 1;
    printf("%lld\n", ans);
    return;
}

void f2(){
    auto get = [&](tuple<int, int, int> A, tuple<int, int, int> B) -> int {
        int a, b, c, x, y, z;
        tie(a, b, c) = A;
        tie(x, y, z) = B;
        return (abs(a-x)+abs(b-y)+abs(c-z));
    };
    vector<tuple<int, int, int>> v;
    m = 0;
    for(int i = 1; i <= n; ++i){
        int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        v.pb({a, b, c});
        umax(m, a);
        umax(m, b);
        umax(m, c);
    }
    if(n <= 1e4){
        int answer = 0;
        for(int i = 0; i < n; ++i)
            for(int j = i+1; j < n; ++j)
                if(get(v[i], v[j]) <= d)
                    answer++;
        printf("%lld\n", answer);
        return;
    }
    vector<vector<vector<int>>> A(m+1, vector<vector<int>> (m+1, vector<int> (m+1, 0)));
    for(int i = 0; i < n; ++i){
        int a, b, c;
        tie(a, b, c) = v[i];
        A[a][b][c]++;
    }
    int answer = 0;
    for(int i = 0; i < n; ++i){
        int x, y, z;
        tie(x, y, z) = v[i];
        for(int a = max(0LL, x-d); a <= min(m, x+d); ++a){
            int dx = d-abs(x-a);
            for(int b = max(0LL, y-dx); b <= min(m, y+dx); ++b){
                int dy = dx-abs(y-b);
                for(int c = max(0LL, z-dy); c <= min(m, z+dy); ++c)
                    answer += A[a][b][c];
            }
        }
        answer--;
    }
    answer >>= 1;
    printf("%lld\n", answer);
}

signed main(){
    scanf("%lld%lld%lld%lld", &b, &n, &d, &m);
    if(b == 1)
        f();
    else if(b == 2)
        f1();
    else
        f2();
    return 0;
}

Compilation message (stderr)

pairs.cpp: In function 'void f()':
pairs.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void f1()':
pairs.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |             scanf("%lld", &j);
      |             ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void f2()':
pairs.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%lld%lld%lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%lld%lld%lld%lld", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 10
• Subtask 13: 0 / 10