| ||||||||||
| 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