Submission #1285008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285008		beka19	Pairs (IOI07_pairs)	C++20	47 / 100	4093 ms	32376 KiB

pairs

    #include <bits/stdc++.h>
using namespace std;
#define sped ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define s second
#define f first
#define int long long
const int N = 1e6 + 1;
int t[N*36],L[N * 36],R[N * 36];
int z[N * 36];
int cntv = 2;
void update(int v,int tl,int tr,int pos){
   if(tl == tr){
        t[v]++;
   }
   else{
     int tm = (tl + tr) / 2;
     if(pos <= tm){
     if(L[v] == 0) L[v] = cntv++;
     update(L[v],tl,tm,pos);
     }
     else{
     if(R[v] == 0) R[v] = cntv++;
     update(R[v],tm+1,tr,pos);
     }
     t[v] = t[L[v]] + t[R[v]];
   }
}
int get(int v,int tl,int tr,int l,int r){
    if(l > r) return 0;
  if(t[v] == 0) return 0;
  if(tl > r || l > tr) return 0;
   if(tl >= l && tr <= r){
       return t[v];
   }
   int tm = (tl + tr) / 2;
   return get(L[v] ,tl,tm,l,r) + get(R[v] ,tm+1,tr,l,r);
}
void okok(){
    int bb;
    cin >> bb;
    int n;
    cin >> n;
    int d;
    cin >> d;
    int m;
    cin >> m;
    if(bb == 1){
        int NN = 1e9;
        int a[n + 1];
        map<int,int>mm;
        for(int i =1;i <= n;i++){
            cin >> a[i];
            mm[a[i]]++;
            update(1,1,NN,a[i]);
        }
        int ans = 0;
        for(int i = 1;i <= n;i++){
            ans += get(1,1,NN,max(1ll,a[i] - d),a[i]-1);
            ans += get(1,1,NN,a[i] + 1,min(a[i] + d,NN));
            ans += mm[a[i]] - 1;
        }
        cout << ans / 2;
        return;

    }
    int a[n + 1];
    int b[n + 1];
    int c[n + 1];
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(bb >= 2){
            cin >> b[i];
        }
        if(bb == 3){
            cin >> c[i];
        }
    }
    int cc = 0;
    for(int i = 1;i <= n;i++){
        for(int j = i + 1;j <= n;j++){
                int ans = 0;
            ans += abs(a[i] - a[j]);
            if(bb >= 2){
                ans += abs(b[i] - b[j]);
             }
            if(bb == 3){
                ans += abs(c[i] - c[j]);
            }
            if(ans <= d)cc++;

        }
    }
    cout << cc;
}
signed main() {
//freopen("bank.in", "r", stdin) ;
//freopen("bansk.out", "w", stdout);
sped
int tt = 1;
//cin >> tt;
while(tt--){
    okok();
    //cout << '\n';
    }
}

• 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: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10