Submission #7427

#	Time	Username	Problem	Language	Result	Execution time	Memory
7427		gs13068	수족관 3 (KOI13_aqua3)	C++98	100 / 100	164 ms	19836 KiB

aqua3

#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;
  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: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16