fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ff first
  4. #define ss second
  5. #define db double
  6. #define ll long long int
  7. #define ull unsigned long long int
  8. #define vs vector<string>
  9. #define vll vector<ll>
  10. #define vul vector<ull>
  11. #define vi vector<int>
  12. #define vb vector<bool>
  13. #define vdb vector<db>
  14. #define vc vector<char>
  15. #define pb push_back
  16. #define ppb pop_back
  17. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  18. const int mod=1e9+7; 
  19. const int mxx=1e5+10;
  20.  
  21. vector<ll> primes,spf,p2,fact,invfact;
  22.  
  23. // precompute all powers of 2
  24. void pow2(ll n,ll m){
  25.     p2.resize(n+2);
  26.     p2[0]=1;
  27.     for(ll i=1;i<n;i++)
  28.         p2[i]=(p2[i-1]*2)%m;
  29. }
  30.  
  31.  
  32. // linear diophantine eqn
  33. ll extendedGCD(ll a,ll b,ll& x,ll& y){
  34.     if(b==0){
  35.         x=1;
  36.         y=0;
  37.         return a;
  38.     }
  39.     ll x1,y1,g;
  40.     g=extendedGCD(b,a%b,x1,y1);
  41.     x=y1;
  42.     y=x1-y1*(a/b);
  43.     return g;
  44. }
  45.  
  46. // find the gcd of a,b
  47. ll gcd(ll a,ll b){
  48.     if(b==0)
  49.         return a;
  50.     return gcd(b,a%b);
  51. }
  52.  
  53. ll getLCM(ll a,ll b){
  54.     return (a*b)/gcd(a,b);
  55. }
  56.  
  57.  
  58. // calCulate Factorial and nCr
  59. void calcFactorial(ll n,ll m){
  60.     fact.resize(n+4);
  61.     invfact.resize(n+4);
  62.  
  63.     fact[0]=1;
  64.     invfact[0]=1;
  65.  
  66.     for(ll i=1;i<n;i++){
  67.         fact[i]=(fact[i-1]*i)%m;
  68.         ll x,y;
  69.         extendedGCD(fact[i],m,x,y);           
  70.         invfact[i]=(x%m+m)%m;
  71.     }
  72. }
  73.  
  74.  
  75. ll nCr(ll n,ll r){
  76.     if(n<r)
  77.         return 0;
  78.     ll ans=(((fact[n]*invfact[r])%mod)*invfact[n-r])%mod;
  79.     return ans;
  80. }
  81.  
  82. ll nPr(ll n,ll r){
  83.     ll ans=(fact[n]*invfact[n-r])%mod;
  84.     return ans;
  85. }
  86.  
  87. // return a^b under mod operation
  88. ll binpow(ll a,ll b,ll m){
  89.     if(b==0)
  90.         return 1;
  91.     ll ans=1;
  92.     if(b&1)
  93.         ans=a%m;
  94.     ll half=binpow(a,b>>1,m);
  95.     half=(half*half)%m;
  96.     return ans=(ans*half)%m;
  97. }
  98.  
  99. // get all primes in [1,n]
  100. void getPrimes(ll n){
  101.     if(n<2)
  102.         return; // no prime less than 2
  103.  
  104.     // spf  contains factorization of all numbers between [1,n]
  105.     spf.resize(n+3);
  106.     for(int i=1;i<=n;i++){
  107.         spf[i]=2;
  108.         if(i&1)
  109.             spf[i]=i;
  110.     }
  111.  
  112.     // p contains all primes between [1,n]
  113.     primes.pb(2);
  114.     for(ll i=3;i<=n;i++){
  115.         if(spf[i]==i){
  116.             primes.pb(i);
  117.             for(ll j=i*i;j<=n;j+=i)
  118.                 spf[j]=i;
  119.         }
  120.     }
  121. }
  122.  
  123. // check if a string is ispalindorme
  124. ll ispalin(string s){
  125.     if(s.length()==0)
  126.         return 0;
  127.     ll i=0,j=s.length()-1;
  128.     while(i<j){
  129.         if(s[i]!=s[j])
  130.             return 0;
  131.         i++;
  132.         j--;
  133.     }
  134.     return 1;
  135. }
  136.  
  137. //  print Y/N
  138. void printYN(int flg){
  139.     if(flg)
  140.         cout<<"YES";
  141.     else
  142.         cout<<"NO";
  143.     cout<<"\n";
  144. }
  145.  
  146. // to get array input
  147. void getArrayInput(vll& a,ll n){
  148.     for(ll i=0;i<n;i++)
  149.         cin>>a[i];
  150. }
  151.  
  152. void getPrefixSum(vll& a,vll& p,ll n){
  153.     if(n){
  154.         p[0]=a[0];
  155.         for(ll i=1;i<n;i++)
  156.             p[i]=p[i-1]+a[i];  
  157.     }
  158. } 
  159.  
  160. void printArray(vll& a,ll n){
  161.     for(ll i=0;i<n;i++)
  162.         cout<<a[i]<<" ";
  163.     cout<<"\n";
  164. }
  165.  
  166. // to get string input
  167. string getStringInput(){
  168.     string s;
  169.     cin>>s;
  170.     return s;
  171. }
  172.  
  173. // DSU 
  174. vector<ll> par,rnk;
  175. void makeParent(ll n){
  176.     for(ll i=0;i<n;i++)
  177.         par[i]=i;
  178. }
  179.  
  180. ll findParent(ll u){
  181.     if(par[u]==u)
  182.         return u;
  183.     return par[u]=findParent(par[u]);
  184. }
  185.  
  186. void Union(ll u,ll v){
  187.     u=findParent(u);
  188.     v=findParent(v);
  189.     if(u!=v){
  190.         if(rnk[u]>rnk[v])
  191.             swap(u,v);
  192.         par[u]=v;
  193.         rnk[v]+=rnk[u];
  194.     }
  195. }
  196.  
  197.  
  198. /*
  199. // LCA 
  200. ll timer,levMax;
  201. vector<ll> tin,tout;
  202. vector<vector<ll>> dp,g; // initialize with -1
  203.  
  204. void dfs(ll u,ll p=-1){
  205.     tin[u]=++timer;
  206.     dp[u][0]=p;
  207.     for(auto v:g[u]){
  208.         if(v!=p)
  209.             dfs(v,u);
  210.     }
  211.     tout[u]=++timer;
  212. }
  213.  
  214. // isAncestor
  215. ll isAncestor(ll u,ll v){
  216.     return tin[u]<=tin[v] and tout[v]<=tout[u];
  217. }
  218.  
  219. // Binary-Lifting
  220. void ConstructLCA(){
  221.     for(ll lev=1;lev<=levMax;lev++){
  222.         for(ll u=0;u<n;u++){
  223.             if(dp[u][lev-1]>=0)
  224.                 dp[u][lev]=dp[dp[u][lev-1]][lev-1];
  225.         }
  226.     }
  227. }
  228.  
  229. ll LCA(ll u,ll v){
  230.     if(isAncestor(u,v))
  231.         return u;
  232.     if(isAncestor(v,u))
  233.         return v;
  234.         
  235.     for(ll i=levMax;i>=0;i--){
  236.         if(!isAncestor(dp[u][i],v))
  237.             u=dp[u][i];
  238.     }
  239.     
  240.     return dp[u][0];
  241. }
  242. */
  243.  
  244. void solver(){   
  245.     ll n;
  246.     cin>>n;
  247.  
  248.     vll a(n);
  249.     getArrayInput(a,n);
  250.     sort(a.begin(),a.end());
  251.  
  252.     vll p(n),s(n);
  253.     p[0]=a[0];
  254.     s[n-1]=a[n-1];
  255.     for(ll i=1;i<n;i++){
  256.         p[i]=p[i-1]+a[i];
  257.         s[n-i-1]=s[n-i]+a[i];
  258.     }
  259.     for(ll i=0;i<n;i++){
  260.         ll j=lower_bound(a.begin(),a.end(),i+1)-a.begin();
  261.         ll mx=0,mn=n-j;
  262.  
  263.         ll k=lower_bound(a.begin(),a.end(),i)-a.begin();
  264.         if(a[k]==i)
  265.         	k--;
  266.  
  267.         if(k>=0)
  268.         	mx=n*(1+k)-p[k];
  269.  
  270.         if(j<n){
  271. 			mx-=s[j];
  272. 			mx+=(n+1)*(n-j);
  273.         }
  274.  
  275. 		cout<<mn<<" "<<mx<<"\n";
  276.     }
  277. }
  278.  
  279. int main(){
  280.     IOS;
  281.     ll t=1;
  282.     cin>>t;
  283.     //calcFactorial(8011,mod);
  284.  
  285.     for(ll tc=1;tc<=t;tc++)
  286.         solver();
  287. }
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
2
1 0
5
3 1 5 0 2
3
1 2 1
stdout
copy 
1 2
0 2
4 13
3 15
2 15
1 13
1 15
3 9
1 2
0 4
https://ideone.com/olIF7J
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!