fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #define dibs reserve
  13. #define OVER9000 1234567890
  14. #define patkan 9
  15. #define tisic 47
  16. #define soclose 10e-7
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define chocolate win
  19. #define ff first
  20. #define ss second
  21. // mylittlepony
  22. using namespace std;
  23.  
  24. struct node {
  25.     int st,end;
  26.     int son[2];
  27.     long long live,mod,val;};
  28.  
  29. struct intervalac {
  30.     vector<node> T;
  31.  
  32.     void constI(int akt) {
  33.         node n =T[akt];
  34.         if(n.st == n.end-1) return;
  35.         for(int i =0; i < 2; i++) {
  36.             if(i == 0) n.end =(n.st+n.end)/2;
  37.             else {n.st =n.end; n.end =T[akt].end;}
  38.             T[akt].son[i] =T.size();
  39.             T.push_back(n);
  40.             constI(T[akt].son[i]);}
  41.         }
  42.  
  43.     intervalac(int N) {
  44.         node n;
  45.         n.st =n.live =n.mod =n.val =0, n.end =N;
  46.         n.son[0] =n.son[1] =-1;
  47.         T.resize(1,n);
  48.         constI(0);}
  49.  
  50.     void darkmagic(int akt) {
  51.         T[akt].val +=T[akt].mod*T[akt].live;
  52.         if(T[akt].son[0] != -1) for(int i =0; i < 2; i++)
  53.             T[T[akt].son[i]].mod +=T[akt].mod;
  54.         T[akt].mod =0;}
  55.  
  56.     void upd1(int akt, int pos) {
  57.         node n =T[akt];
  58.         if(n.st > pos || n.end <= pos) return;
  59.         darkmagic(akt);
  60.         T[akt].live++;
  61.         if(n.son[0] != -1) {
  62.             T[akt].val =0;
  63.             for(int i =0; i < 2; i++) {
  64.                 upd1(n.son[i],pos);
  65.                 T[akt].val +=get(n.son[i],T[n.son[i]].st,T[n.son[i]].end);}}
  66.         }
  67.  
  68.     void upd2(int akt, int st, int end, long long val) {
  69.         node n =T[akt];
  70.         if(n.st >= end || n.end <= st) return;
  71.         if(n.st == st && n.end == end) {
  72.             T[akt].mod +=val;
  73.             darkmagic(akt);
  74.             return;}
  75.         darkmagic(akt);
  76.         T[akt].val =0;
  77.         for(int i =0; i < 2; i++) {
  78.             upd2(n.son[i],max(T[n.son[i]].st,st),min(T[n.son[i]].end,end),val);
  79.             T[akt].val +=T[n.son[i]].val;}
  80.         }
  81.  
  82.     long long get(int akt, int st, int end) {
  83.         node n =T[akt];
  84.         if(n.st >= end || n.end <= st) return 0;
  85.         darkmagic(akt);
  86.         if(n.st == st && n.end == end) return T[akt].val;
  87.         return get(n.son[0],st,min(end,(n.st+n.end)/2))+get(n.son[1],max(st,(n.st+n.end)/2),end);
  88.         }
  89.     };
  90.  
  91. struct fin {
  92.     vector<long long> T;
  93.     fin(int N) {T.resize(N+1,0);}
  94.  
  95.     int lastone(int x) {return x&(x^(x-1));}
  96.  
  97.     void upd(int pos, long long val) {
  98.         for(int i =pos+1; i < T.size(); i +=lastone(i)) T[i] +=val;}
  99.  
  100.     long long get(int pos) {
  101.         long long ret =0;
  102.         for(int i =pos+1; i > 0; i -=lastone(i)) ret +=T[i];
  103.         return ret;}
  104.     };
  105.  
  106. struct info {
  107.     int r,t,id;
  108.  
  109.     bool operator<(const info &A) const {
  110.         if(r != A.r) return r < A.r;
  111.         return t < A.t;}
  112.     };
  113.  
  114. long long GCD(long long a, long long b) {
  115.     if(a > b) swap(a,b);
  116.     if(a == 0) return b;
  117.     return GCD(b%a,a);}
  118.  
  119. int main() {
  120.     int T,N;
  121.     cin >> T;
  122.     for(int t =0; t < T; t++) {
  123.         cin >> N;
  124.         vector< pair<int,string> > A0(N);
  125.         map<string,int> Mt;
  126.         map<int,int> Mr;
  127.         for(int i =0; i < N; i++) {
  128.             cin >> A0[i].ss >> A0[i].ff;
  129.             Mt[A0[i].ss] =0;
  130.             Mr[-A0[i].ff] =0;}
  131.         int a =0;
  132.         ALL_THE(Mr,it) {it->ss =a; a++;}
  133.         a =0;
  134.         ALL_THE(Mt,it) {it->ss =a; a++;}
  135.         vector<info> A(N);
  136.         for(int i =0; i < N; i++) {
  137.             A[i].r =Mr[-A0[i].ff];
  138.             A[i].t =Mt[A0[i].ss];
  139.             A[i].id =i;}
  140.         sort(A.begin(),A.end());
  141.  
  142.         vector<long long> Ti(N,0);
  143.  
  144.         // newbie
  145.         fin Kn(N+patkan);
  146.         fin Sn(N+patkan);
  147.         for(int i =N-1; i >= 0; i--) {
  148.             long long K =Kn.get(A[i].t-1);
  149.             Ti[A[i].id] =K*(K-1)/2-Sn.get(A[i].t-1);
  150.             Sn.upd(A[i].t,Kn.get(A[i].t));
  151.             Kn.upd(A[i].t,1);}
  152.  
  153.         for(int i =0; i < N; i++) A[i].t =a-1-A[i].t;
  154.         for(int k =0; k < 2; k++) {
  155.             for(int i =0; i < N; i++) swap(A[i].t,A[i].r);
  156.             sort(A.begin(),A.end());
  157.             // wild or experienced
  158.             fin Ko(N+patkan);
  159.             fin So(N+patkan);
  160.             intervalac I(N+patkan);
  161.             vector<long long> K(N);
  162.  
  163.             for(int i =0; i < N; i++) {
  164.                 K[i] =Ko.get(A[i].t-1);
  165.                 long long S =So.get(N+1)-So.get(A[i].t);
  166.                 long long X =I.get(0,A[i].t,N+1);
  167.                 Ti[A[i].id] +=S-X;
  168.                 if(i < N-1) if(A[i].r == A[i+1].r) continue;
  169.                 for(int j =i; j >= 0; j--) {
  170.                		if(A[j].r != A[i].r) break;
  171. 	                Ko.upd(A[j].t,1);
  172. 	                So.upd(A[j].t,K[j]);
  173. 					I.upd2(0,0,A[j].t,1);
  174.                		I.upd1(0,A[j].t);}}
  175.             }
  176.  
  177.         long long Tt =0;
  178.         for(int i =0; i < N; i++) {
  179.         	if(Ti[i] < 0) Ti[i] *=-1;
  180.         	Tt +=Ti[i];}
  181.         if(Tt == 0) cout << "Rules Should Be Changed!";
  182.         else for(int i =0; i < N; i++) {
  183.             long long d =GCD(Tt,Ti[i]*3);
  184.             if(i > 0) cout << " ";
  185.             cout << Ti[i]*3/d << "/" << Tt/d;}
  186.         cout << "\n";}
  187.     return 0;}
  188.  
  189. // look at my code
  190. // my code is amazing
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
1
18
3 270765835
3 413879223
1 254146067
0 672003067
0 313951506
1 472317364
0 13162878
2 320679874
1 680928155
3 8567160
4 517041421
0 368669870
0 111111224
4 221960279
1 21247247
4 624454527
0 480906039
3 969809367
2 713974233
4 253539013
stdout
copy 
11/84 5/42 5/28 1/21 1/6 13/84 1/28 19/84 1/84 1/4 9/28 4/21 5/42 1/21 23/84 9/28 3/14 4/21
https://ideone.com/vos4a4
language:
C++14 (gcc 8.3)
created:
11 years 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!