Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 官方数据都调对了呀...为什么还是WA？哪位大牛帮忙看看

Posted by doggy at 2007-10-18 10:12:13 on Problem 3149
```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const long long lim=(long long) 100000*100000;
struct stats {
long long l,r;
char cost[25];
};

stats s[20000],q[20000];
long long k1,k2,base,all,j,n,lot,st,fin;
char name[25],cst[25];
long long ans[100000];
char nans[100000][25];

bool comparestat(stats a,stats b) {
return a.l<b.l;
}

void scopy(char c1[],char c2[]) {
memset(c1,0,25);
for (long i=0;i<strlen(c2);i++) c1[i]=c2[i];
}

void ins_segment(long long l_,long long r_,char cost_[]) {
all++;
s[all].l=l_;
s[all].r=r_;
scopy(s[all].cost,cost_);
}

void del_segment(long k) {
s[k].l=s[all].l;
s[k].r=s[all].r;
scopy(s[k].cost,s[all].cost);
memset(s[all].cost,0,25);
all--;
}

void work(long long nq,long long &ns) {
if (q[nq].l>s[ns].r || s[ns].l>q[nq].r) {
ns++;
return;
}
if (s[ns].l<q[nq].l) ins_segment(s[ns].l,q[nq].l-1,s[ns].cost);
if (q[nq].r<s[ns].r) ins_segment(q[nq].r+1,s[ns].r,s[ns].cost);
del_segment(ns);
}

void take_suffix(long long l,long long r,long long code) {
long long base=1,suf,lb,rb;
while (l<=r) {
while (base*10<=l && base<lim) base*=10;
while (base>0) {
suf=l/base;
lb=suf*base;
rb=lb+base-1;
if (l<=lb && rb<=r) {
lot++;
ans[lot]=suf;
scopy(nans[lot],s[code].cost);
l=rb+1;
break;
} else {
base/=10;
}
}
}
}

void convert(long long &k,char p[]) {
k=0;
for (long i=0;i<strlen(p);i++) k=k*10+long(p[i])-48;
}

int main() {
long kase=0;
freopen("21","r",stdin);
freopen("output.txt","w",stdout);
while (cin>>n) {
for (long i=1;i<=n;i++) {
char blank;
cin>>cst>>blank>>fin>>name;
convert(st,cst);
k1=st;k2=fin;
base=1;
while (k1>0 && k2>0) {
k1/=10;
k2/=10;
base*=10;
}
fin=k1*base+fin;
for (long j=1;j<=11-strlen(cst);j++) {
fin=fin*10+9;st*=10;
}
q[i].l=st+lim*10;q[i].r=fin+lim*10;
scopy(q[i].cost,name);
}
all=0;
for (long i=n;i>=1;i--) {
j=1;
while (j<=all) work(i,j);
if (strcmp(q[i].cost,"invalid")!=0) {
all++;
s[all].l=q[i].l;
s[all].r=q[i].r;
scopy(s[all].cost,q[i].cost);
}
}
sort(&s[1],&s[all+1],comparestat);
long long now=(all>=1)?1:0;
for (long i=2;i<=all;i++) {
if (strcmp(s[i].cost,s[now].cost)==0 && s[i].l<=s[now].r+1) s[now].r=s[i].r; else {
now++;
s[now].l=s[i].l;
s[now].r=s[i].r;
if (now!=i) scopy(s[now].cost,s[i].cost);
}
}
lot=0;
for (long long i=1;i<=now;i++) {
long long ll=s[i].l,rr=s[i].r;
take_suffix(ll,rr,i);
}
cout<<lot<<endl;
long dog[20];
for (long long i=1;i<=lot;i++) {
memset(dog,0,sizeof(dog));
long long tmp=ans[i];
while (tmp!=0) {
dog[++dog[0]]=tmp%10;
tmp/=10;
}
for (long j=dog[0]-1;j>=1;j--) cout<<dog[j];
cout<<' '<<nans[i]<<endl;
}
}
}```

Followed by: