ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1316. Electronic Auction

i got wa on test 6
Posted by collin 16 Apr 2004 08:57
what's wrong on earth?
thanks all
Re: i got wa on test 6
Posted by @FEAR 2 Jun 2004 13:22
First I got WA ON 5.
I changed longint into int64 then WA ON 6 :(
Then changed trunc into round,got AC.
Thank you very much!I got AC,too.
Posted by Neumann 31 Jan 2005 13:11
Re: Thank you very much!I got AC,too.
Posted by Hard ( DHSP ) 1 Jul 2005 11:24
Round what ? Can you explain ?
I use Int64, too .
I write result : Writeln(Profit/100:0:2) ;
Why it's wrong ?
How get AC?
Posted by QQQQ 10 Jun 2006 00:07
I use long long int type and rigth read-write operations. But also have WA#6. Who can help me?

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define left(x) ((x) << 1)
#define right(x) ((x) << 1 | 1)
#define parent(x) ((x) >> 1)

enum CmdType {BID,DEL,SALE};

struct
{
int price,c;
enum CmdType cmd;
} data;
struct
{
int l,r,v;
} tree;
int n,size,sz,bnd,bnds,bndc,bndsc;
char buf;

int query(int price)
{
int ans = 0;
int v = 1;
while (v < sz && tree[v].v > 0)
if (price <= tree[left(v)].r)
v = left(v);
else
{
ans += tree[left(v)].v;
v = right(v);
}
return ans+tree[v].v;
}

void add(int price, int delta)
{
int v = 1;
while (v < sz)
{
tree[v].v += delta;
if (price <= tree[left(v)].r)
v = left(v);
else
v = right(v);
}
tree[v].v += delta;
}

void main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt","r",stdin);
#endif
n = bndsc = 0;
bnds[bndsc++] = 0;
bnds[bndsc++] = 1000000;
while (true)
{
gets(buf);
if (buf == 'Q')
break;
double t;
if (buf == 'S')
{
sscanf(buf+4,"%lf%d",&t,&data[n].c);
data[n].cmd = SALE;
}
else
{
sscanf(buf+4,"%lf",&t);
if (buf == 'B')
data[n].cmd = BID;
else
data[n].cmd = DEL;
}
data[n].price = 1000000-floorl(t*100.0+0.3);
if (data[n].cmd == SALE)
bnds[bndsc++] = data[n].price;
n++;
}
sort(bnds,bnds+bndsc);
bnd = bnds;
bndc = 1;
for (int i = 1; i < bndsc; i++)
if (bnds[i] != bnds[i-1])
bnd[bndc++] = bnds[i];
bndc--;
for (sz = 1; sz < bndc; sz*=2);
for (int i = 0; i < bndc; i++)
{
tree[sz+i].l = bnd[i]+1;
tree[sz+i].r = bnd[i+1];
tree[sz+i].v = 0;
}
for (int i = sz-1; i >= 1; i--)
{
tree[i].l = tree[left(i)].l;
tree[i].r = tree[right(i)].r;
tree[i].v = 0;
}

long long ans = 0;
for (int i = 0; i < n; i++)
if (data[i].cmd == SALE)
{
int v = query(data[i].price);
if (v > data[i].c) v = data[i].c;
ans += v;
}
else if (data[i].cmd == BID)