oj.uz

Submission #7425

# Submission time Handle Problem Language Result Execution time Memory
7425 2014-08-05T06:24:58 Z gs13068 수족관 3 (KOI13_aqua3) C++
0 / 100
 168 ms 11276 KB 
#include<cstdio>
#include<set>
#include<algorithm>

#define OFFSET 262144

struct tree
{
  int x;
  int y;
} tr[600000];

int x[200000];
int y[200000];
int z[200000];

void init(){int i;for(i=0;i<600000;i++){tr[i].x=1e9;tr[i].y=i-OFFSET;}}
void update(int x,int y){x+=OFFSET;for(tr[x].x=y;x;x>>=1)if(tr[x>>1].x>y){tr[x>>1].x=y;tr[x>>1].y=tr[x].y;}}
int where(int x,int y){int r=1e9,ri;for(x+=OFFSET,y+=OFFSET;x<=y;x=(x+1)>>1,y=(y-1)>>1){if(tr[x].x<r){r=tr[x].x;ri=tr[x].y;}if(tr[y].x<r){r=tr[y].x;ri=tr[y].y;}}return ri;}

std::multiset<long long> S;
std::multiset<long long>::iterator it;

long long dfs(int l,int r,int d)
{
  if(l>r)return 0LL;
  if(l==r)
  {
    S.insert(1LL*(x[r+1]-x[l])*(y[l]-d));
    return 1LL*(x[r+1]-x[l])*(y[l]-d);
  }
  long long ll,rr;
  int mid=where(l,r),cnt;
  printf("%d %d %d\n",l,r,mid);
  ll=dfs(l,mid-1,y[mid]);
  rr=dfs(mid+1,r,y[mid]);
  if(ll<rr)ll^=rr^=ll^=rr;
  S.erase(S.find(ll));
  S.insert(ll+1LL*(x[r+1]-x[l])*(y[mid]-d));
  return ll+1LL*(x[r+1]-x[l])*(y[mid]-d);
}

int main()
{
  long long res=0;
  int i,n,m;
  scanf("%d",&n);
  n>>=1;
  n--;
  init();
  for(i=0;i<=n;i++)
  {
    scanf("%*d%*d%d%d",&x[i],&y[i]);
    update(i,y[i]);
  }
  scanf("%d",&m);
  dfs(0,n-1,0);
  for(i=0;i<m&&!S.empty();i++)
  {
    it=S.end();
    it--;
    res+=*it;
    S.erase(it);
  }
  printf("%lld",res);
}

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 8240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 8240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 11276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 11276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 11276 KB Output isn't correct
2 Halted 0 ms 0 KB -