oj.uz

Submission #599740

# Submission time Handle Problem Language Result Execution time Memory
599740 2022-07-19T20:00:26 Z gg123_pe Pairs (IOI07_pairs) C++14
60 / 100
 103 ms 7484 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef pair <pair<char,char>, pair<char,char>> T; 
#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 150005, M = 75001; 

int b, n, d, m, bit[N];
vector <vector <int>> a;
ll ans; 

void upd(int u, int val){
    for(; u < N; u = (u|(u+1))) bit[u] += val; 
}

int get(int u){
    int res = 0;
    for(; u >= 0; u = (u&(u+1)) - 1) res += bit[u];  
    return res;
}

int que(int l, int r){ return get(r) - get(l-1); }

int main(){
    cin >> b >> n >> d >> m; 

    a.resize(n); 

    f(i,0,n) {
        a[i].resize(b); 
        f(j,0,b) cin >> a[i][j];
    }

    if(b == 1){
        sort(a.begin(), a.end()); 

        int l = 0; 
        f(i,0,n){ 
            while(a[i][0] - a[l][0] > d) l++;
            ans += (ll) (i - l); 
        }
        cout << ans << "\n"; 
        return 0; 
    }
    if(b == 2){
        f(i,0,n){
            int u = a[i][0] + a[i][1], v = a[i][0] - a[i][1] + M; 
            a[i][0] = u, a[i][1] = v; 
        }
        sort(a.begin(), a.end()); 

        int l = 0; 
        f(i,0,n){
            while(a[i][0] - a[l][0] > d){
                upd(a[l][1], -1);
                l++; 
            }
            ans += (ll) que(max(0, a[i][1] - d), min(N-1, a[i][1]+d));
            upd(a[i][1], 1);
        }
        cout << ans << "\n"; 
        return 0; 
    }
   
    cout << ans << "\n";
    return 0; 
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6088 KB Output is correct
2 Correct 39 ms 6156 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6640 KB Output is correct
2 Correct 62 ms 6644 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6648 KB Output is correct
2 Correct 64 ms 6648 KB Output is correct
3 Correct 72 ms 6556 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6260 KB Output is correct
2 Correct 60 ms 6256 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 6552 KB Output is correct
2 Correct 79 ms 6464 KB Output is correct
3 Correct 83 ms 6512 KB Output is correct
4 Correct 78 ms 6592 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7484 KB Output is correct
2 Correct 83 ms 7372 KB Output is correct
3 Correct 103 ms 7412 KB Output is correct
4 Correct 92 ms 7444 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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