oj.uz

Submission #1060605

# Submission time Handle Problem Language Result Execution time Memory
1060605 2024-08-15T18:48:31 Z KasymK Pairs (IOI07_pairs) C++17
80 / 100
 4000 ms 101460 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 75352 KB Output is correct
2 Correct 10 ms 75356 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 77008 KB Output is correct
2 Correct 20 ms 77048 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 77268 KB Output is correct
2 Correct 24 ms 77264 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 77264 KB Output is correct
2 Correct 25 ms 77260 KB Output is correct
3 Correct 23 ms 77264 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 75872 KB Output is correct
2 Correct 13 ms 75920 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 88148 KB Output is correct
2 Correct 138 ms 88148 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 89876 KB Output is correct
2 Correct 136 ms 90608 KB Output is correct
3 Correct 114 ms 89424 KB Output is correct
4 Correct 123 ms 89172 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 98244 KB Output is correct
2 Correct 293 ms 101460 KB Output is correct
3 Correct 154 ms 90704 KB Output is correct
4 Correct 147 ms 90196 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 75612 KB Output is correct
2 Correct 11 ms 75536 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 79824 KB Output is correct
2 Correct 94 ms 79308 KB Output is correct
3 Correct 95 ms 79304 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 80576 KB Output is correct
2 Execution timed out 4016 ms 80516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2104 ms 82308 KB Output is correct
2 Execution timed out 4046 ms 82376 KB Time limit exceeded
3 Halted 0 ms 0 KB -