oj.uz

Submission #7427

# Submission time Handle Problem Language Result Execution time Memory
7427 2014-08-05T06:26:43 Z gs13068 수족관 3 (KOI13_aqua3) C++
100 / 100
 164 ms 19836 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;
  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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8240 KB Output is correct
2 Correct 0 ms 8240 KB Output is correct
3 Correct 0 ms 8240 KB Output is correct
4 Correct 0 ms 8240 KB Output is correct
5 Correct 0 ms 8240 KB Output is correct
6 Correct 4 ms 8240 KB Output is correct
7 Correct 4 ms 8240 KB Output is correct
8 Correct 0 ms 8240 KB Output is correct
9 Correct 0 ms 8240 KB Output is correct
10 Correct 0 ms 8240 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8240 KB Output is correct
2 Correct 0 ms 8240 KB Output is correct
3 Correct 0 ms 8240 KB Output is correct
4 Correct 0 ms 8240 KB Output is correct
5 Correct 0 ms 8240 KB Output is correct
6 Correct 0 ms 8312 KB Output is correct
7 Correct 4 ms 8240 KB Output is correct
8 Correct 0 ms 8240 KB Output is correct
9 Correct 0 ms 8240 KB Output is correct
10 Correct 4 ms 8240 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 11276 KB Output is correct
2 Correct 140 ms 11276 KB Output is correct
3 Correct 152 ms 12880 KB Output is correct
4 Correct 156 ms 12972 KB Output is correct
5 Correct 144 ms 12972 KB Output is correct
6 Correct 120 ms 19828 KB Output is correct
7 Correct 144 ms 17408 KB Output is correct
8 Correct 144 ms 17408 KB Output is correct
9 Correct 156 ms 10484 KB Output is correct
10 Correct 164 ms 10484 KB Output is correct
11 Correct 120 ms 19836 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 11276 KB Output is correct
2 Correct 140 ms 11276 KB Output is correct
3 Correct 164 ms 13096 KB Output is correct
4 Correct 148 ms 12828 KB Output is correct
5 Correct 164 ms 12964 KB Output is correct
6 Correct 116 ms 19832 KB Output is correct
7 Correct 152 ms 17408 KB Output is correct
8 Correct 144 ms 17404 KB Output is correct
9 Correct 156 ms 10484 KB Output is correct
10 Correct 164 ms 10484 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 11276 KB Output is correct
2 Correct 144 ms 11276 KB Output is correct
3 Correct 160 ms 13072 KB Output is correct
4 Correct 152 ms 13104 KB Output is correct
5 Correct 148 ms 12960 KB Output is correct
6 Correct 152 ms 17408 KB Output is correct
7 Correct 152 ms 17404 KB Output is correct
8 Correct 160 ms 10484 KB Output is correct
9 Correct 164 ms 10484 KB Output is correct