Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
线段树+高精度0ms1A#include <iostream> #include <stdio.h> using namespace std; void buildTree(int s, int e, int *src, int numb){ src[numb] = e-s+1; if(s==e) return; int mid = (s+e)/2; buildTree(s,mid,src,2*numb+1); buildTree(mid+1,e,src,2*numb+2); } void del(int s, int e, int *src, int numb, int pos){ src[numb]--; if(s==e) return; int mid = (s+e)/2; if(pos<=mid) del(s,mid,src,2*numb+1,pos); else del(mid+1,e,src,2*numb+2,pos); } int query(int qs, int qe, int s, int e, int *src, int numb){ if(qe<qs) return 0; if(qs==s && qe==e) return src[numb]; int mid = (s+e)/2; if(qe<=mid) return query(qs,qe,s,mid,src,2*numb+1); if(qs>mid) return query(qs,qe,mid+1,e,src,2*numb+2); return query(qs,mid,s,mid,src,2*numb+1)+query(mid+1,qe,mid+1,e,src,2*numb+2); } int main() { char fei, ks; bool dyg = 1; while(1){ cin >> ks; if(ks == '-') { cout << endl; return 0; } if(!dyg) cout << ","; dyg = 0; int n; cin >> n; cin >> fei >> fei; int lst[55]; for(int i = 1; i <= n; i++){ cin >> lst[i] >> fei; } //for(int i = 1; i <= n; i++) cout << lst[i] << " "; cout << endl; cin >> fei; if(n==1) { cout << 1; continue; } int xds[500]; buildTree(1, n, xds, 0); int q[500]; for(int i = 1; i < n; i++){ q[i] = query(1,lst[i]-1,1,n,xds,0); del(1,n,xds,0,lst[i]); } //for(int i = 1; i < n; i++) cout << q[i] << " "; cout << endl; int gjd[500] = {0}; int ws = 1; for(int i = 1; i < n; i++){ gjd[0] += (q[i] + (i==n-1 ? 1 : 0)); if(n-i-1){ for(int j = 0; j < ws; j++){ gjd[j] *= (n-i); } } int carry = 0; for(int j = 0; j < ws; j++){ gjd[j] += carry; carry = gjd[j]/10; gjd[j]%=10; } while(carry){ gjd[ws] = carry; carry = gjd[ws]/10; gjd[ws]%=10; ws++; } } for(int i = ws-1; i >= 0; i--){ cout << gjd[i]; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator