oj.uz

Submission #7429

# Submission time Handle Problem Language Result Execution time Memory
7429 2014-08-05T06:34:24 Z gs13068 수족관 3 (KOI13_aqua3) C++
100 / 100
 144 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];

inline void init(){int i;for(i=0;i<OFFSET<<1;i++){tr[i].x=1e9;tr[i].y=i-OFFSET;}}
inline 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;}}
inline 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);
}

inline int getnum()
{
  int t,r=0;
  do{t=getchar();}while(t<40);
  for(r=t-48;(t=getchar())>40;r=r*10+t-48);
  return r;
}

int main()
{
  long long res=0;
  int i,n,m;
  n=getnum();
  n>>=1;
  n--;
  init();
  for(i=0;i<=n;i++)
  {
    getnum();getnum();
    x[i]=getnum();y[i]=getnum();
    update(i,y[i]);
  }
  m=getnum();
  dfs(0,n-1,0);
  for(it=S.end(),i=0;i<m&&it!=S.begin();i++)
  {
    it--;
    res+=*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 0 ms 8240 KB Output is correct
7 Correct 0 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 0 ms 8240 KB Output is correct
2 Correct 4 ms 8240 KB Output is correct
3 Correct 4 ms 8240 KB Output is correct
4 Correct 4 ms 8240 KB Output is correct
5 Correct 4 ms 8240 KB Output is correct
6 Correct 0 ms 8312 KB Output is correct
7 Correct 0 ms 8240 KB Output is correct
8 Correct 4 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 116 ms 11276 KB Output is correct
2 Correct 112 ms 11276 KB Output is correct
3 Correct 132 ms 12876 KB Output is correct
4 Correct 128 ms 12968 KB Output is correct
5 Correct 132 ms 12972 KB Output is correct
6 Correct 80 ms 19836 KB Output is correct
7 Correct 128 ms 17404 KB Output is correct
8 Correct 124 ms 17404 KB Output is correct
9 Correct 140 ms 10484 KB Output is correct
10 Correct 132 ms 10484 KB Output is correct
11 Correct 96 ms 19832 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 120 ms 11276 KB Output is correct
3 Correct 124 ms 13104 KB Output is correct
4 Correct 112 ms 12828 KB Output is correct
5 Correct 128 ms 12964 KB Output is correct
6 Correct 88 ms 19832 KB Output is correct
7 Correct 128 ms 17408 KB Output is correct
8 Correct 132 ms 17408 KB Output is correct
9 Correct 136 ms 10484 KB Output is correct
10 Correct 128 ms 10484 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 11276 KB Output is correct
2 Correct 120 ms 11276 KB Output is correct
3 Correct 124 ms 13072 KB Output is correct
4 Correct 132 ms 13104 KB Output is correct
5 Correct 140 ms 12956 KB Output is correct
6 Correct 132 ms 17408 KB Output is correct
7 Correct 112 ms 17404 KB Output is correct
8 Correct 140 ms 10484 KB Output is correct
9 Correct 144 ms 10484 KB Output is correct