oj.uz

Submission #229229

# Submission time Handle Problem Language Result Execution time Memory
229229 2020-05-03T21:16:35 Z VEGAnn Spiderman (COCI20_spiderman) C++14
70 / 70
 480 ms 14444 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 300100;
const int M = 1000100;
vector<int> vc;
int n, k, a[M], kol[M], mem[M];
bool was[M];

int main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);
    
    cin >> n >> k;
    
    for (int i = 0; i < n; i++){
        cin >> a[i];
        kol[a[i]]++;
        vc.PB(a[i]);
    }
    
    sort(all(vc));
    
    for (int i = 0; i < n; i++){
        if (a[i] < k) {
            cout << "0 ";
            continue;
        }
        
        if (was[a[i]]){
            cout << mem[a[i]] << " ";
            continue;
        }
        
        int ans = 0;
        
        if (a[i] > k){
            int vl = a[i] - k;
        
            for (int i = 1; i * i <= vl; i++)
                if (vl % i == 0){
                    if (k < i) ans += kol[i];
                
                    if (vl / i != i && k < vl / i)
                        ans += kol[vl / i];
                }
        }  else ans = n - (upper_bound(all(vc), a[i]) - vc.begin());
        
        if (k == 0)
            ans--;
        
        mem[a[i]] = ans;
        was[a[i]] = 1;
        
        cout << ans << " ";
    }
    
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5888 KB Output is correct
2 Correct 10 ms 4096 KB Output is correct
3 Correct 39 ms 7932 KB Output is correct
4 Correct 92 ms 11240 KB Output is correct
5 Correct 400 ms 11124 KB Output is correct
6 Correct 423 ms 14444 KB Output is correct
7 Correct 448 ms 11252 KB Output is correct
8 Correct 449 ms 11004 KB Output is correct
9 Correct 480 ms 14440 KB Output is correct
10 Correct 476 ms 14408 KB Output is correct