| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123039 |
2019-06-30T05:42:33 Z |
ansol4328 |
수족관 2 (KOI13_aqua2) |
C++11 |
|
721 ms |
51300 KB |
#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1e9;
struct SegTree
{
vector<int> hole, lwall, rwall, wheight, wlazy;
vector<double> time, lazy;
int base;
SegTree(int a)
{
base=1;
while(base<a) base<<=1;
hole.resize(base*2+2);
lwall.resize(base*2+2); //maximize
rwall.resize(base*2+2,INF); //minimize
time.resize(base*2+2);
lazy.resize(base*2+2);
wheight.resize(base*2+2);
wlazy.resize(base*2+2);
base--;
}
void update_hole(int idx, int val)
{
idx+=base;
hole[idx]+=val;
idx>>=1;
while(idx!=0)
{
hole[idx]=hole[idx*2]+hole[idx*2+1];
idx>>=1;
}
}
int hole_num(int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
if(nf<st || fn<ns) return 0;
if(st<=ns && nf<=fn) return hole[num];
int mid=(ns+nf)>>1;
return hole_num(st,fn,ns,mid,num*2)+hole_num(st,fn,mid+1,nf,num*2+1);
}
int get_lwall(int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
if(nf<st || fn<ns) return 0;
if(st<=ns && nf<=fn) return lwall[num];
int mid=(ns+nf)>>1;
return max(get_lwall(st,fn,ns,mid,num*2),get_lwall(st,fn,mid+1,nf,num*2+1));
}
void update_wall(int idx)
{
int val=idx;
idx+=base;
lwall[idx]=val;
rwall[idx]=val;
idx>>=1;
while(idx!=0)
{
lwall[idx]=max(lwall[idx*2],lwall[idx*2+1]);
rwall[idx]=min(rwall[idx*2],rwall[idx*2+1]);
idx>>=1;
}
}
int get_rwall(int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
if(nf<st || fn<ns) return INF;
if(st<=ns && nf<=fn) return rwall[num];
int mid=(ns+nf)>>1;
return min(get_rwall(st,fn,ns,mid,num*2),get_rwall(st,fn,mid+1,nf,num*2+1));
}
void propagate(int ns, int nf, int num)
{
if(lazy[num]!=0)
{
if(ns<nf)
{
lazy[num*2]+=lazy[num];
lazy[num*2+1]+=lazy[num];
}
time[num]+=lazy[num];
lazy[num]=0;
}
}
void add_time(double val, int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
propagate(ns,nf,num);
if(nf<st || fn<ns) return;
if(st<=ns && nf<=fn)
{
lazy[num]=val;
propagate(ns,nf,num);
return;
}
int mid=(ns+nf)>>1;
add_time(val,st,fn,ns,mid,num*2);
add_time(val,st,fn,mid+1,nf,num*2+1);
time[num]=time[num*2]+time[num*2+1];
}
void pro_height(int ns, int nf, int num)
{
if(wlazy[num]!=0)
{
if(ns<nf)
{
wlazy[num*2]=max(wlazy[num*2],wlazy[num]);
wlazy[num*2+1]=max(wlazy[num*2+1],wlazy[num]);
}
wheight[num]=max(wheight[num],wlazy[num]);
wlazy[num]=0;
}
}
void change_height(int val, int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
pro_height(ns,nf,num);
if(nf<st || fn<ns) return;
if(st<=ns && nf<=fn)
{
wlazy[num]=max(wlazy[num],val);
pro_height(ns,nf,num);
return;
}
int mid=(ns+nf)>>1;
change_height(val,st,fn,ns,mid,num*2);
change_height(val,st,fn,mid+1,nf,num*2+1);
wheight[num]=max(wheight[num*2],wheight[num*2+1]);
}
int get_height(int st, int fn, int ns=1, int nf=-1, int num=1)
{
if(nf==-1) nf=base+1;
pro_height(ns,nf,num);
if(nf<st || fn<ns) return 0;
if(st<=ns && nf<=fn) return wheight[num];
int mid=(ns+nf)>>1;
return max(get_height(st,fn,ns,mid,num*2),get_height(st,fn,mid+1,nf,num*2+1));
}
};
struct in
{
int st, fn, height;
in() {}
in(int a, int b, int c) : st(a), fn(b), height(c) {}
};
bool cmp(const in &x, const in &y)
{
return x.height<y.height || (x.height==y.height && x.st<y.st);
}
int n;
int m[300005][2], h, w;
in line[150005];
int hn, hcnt[500005];
int main()
{
int c=0;
ll tot=0;
scanf("%d",&n);
scanf("%d %d",&m[1][0],&m[1][1]);
m[1][0]++;
for(int i=2 ; i<n ; i+=2)
{
scanf("%d %d",&m[i][0],&m[i][1]);
scanf("%d %d",&m[i+1][0],&m[i+1][1]);
m[i][0]++, m[i+1][0]++;
line[++c]=in(m[i][0],m[i+1][0],m[i][1]);
tot+=(ll)(m[i+1][0]-m[i][0])*(ll)m[i][1];
}
scanf("%d %d",&m[n][0],&m[n][1]);
m[n][0]++;
w=m[n][0];
scanf("%d",&hn);
for(int i=1 ; i<=hn ; i++)
{
int x1, y1, x2 ,y2;
scanf("%d %d",&x1,&y1);
scanf("%d %d",&x2,&y2);
x1++, x2++;
hcnt[x1]++;
}
SegTree T(w);
for(int i=1 ; i<=w ; i++)
{
if(hcnt[i]!=0) T.update_hole(i,hcnt[i]);
}
sort(line+1,line+1+c,cmp);
T.update_wall(1);
T.update_wall(w);
int idx=1;
while(idx<=c)
{
ll leak=0;
ll cur_height=line[idx].height;
queue<P> Q;
int l=-1, r=-1;
do
{
int st=line[idx].st, fn=line[idx].fn;
int lw=T.get_lwall(1,st);
int rw=T.get_rwall(fn,w);
ll wh=T.get_height(lw,rw-1);
Q.push(P(st,fn));
if(l!=lw)
{
l=lw, r=rw;
int hole_num=T.hole_num(l,r-1);
if(hole_num>0)
{
ll block=(ll)(r-l)*(cur_height-wh);
leak+=block;
double val=(double)block/hole_num;
T.add_time(val,l,r-1);
T.change_height((int)cur_height,l,r-1);
}
}
idx++;
}while(line[idx].height==line[idx-1].height);
tot-=leak;
while(!Q.empty())
{
P wval=Q.front();
Q.pop();
T.update_wall(wval.first);
T.update_wall(wval.second);
}
}
int base=T.base, num=0;
for(int len=base+1 ; len>=1 ; len>>=1)
{
for(int st=1 ; st<=base-len+2 ; st+=len)
{
int fn=st+len-1;
num++;
T.propagate(st,fn,num);
}
}
double rest=0;
for(int i=1 ; i<=w ; i++) if(hcnt[i]!=0) rest=max(rest,T.time[i+base]);
printf("%.2lf\n",rest);
printf("%lld",tot);
return 0;
}
Compilation message
aqua2.cpp: In function 'int main()':
aqua2.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua2.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m[1][0],&m[1][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m[i][0],&m[i][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m[i+1][0],&m[i+1][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m[n][0],&m[n][1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&hn);
~~~~~^~~~~~~~~~
aqua2.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x1,&y1);
~~~~~^~~~~~~~~~~~~~~~~
aqua2.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x2,&y2);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
380 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
352 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
380 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
3 ms |
376 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
39288 KB |
Output is correct |
| 2 |
Correct |
48 ms |
38652 KB |
Output is correct |
| 3 |
Correct |
48 ms |
39416 KB |
Output is correct |
| 4 |
Correct |
45 ms |
38392 KB |
Output is correct |
| 5 |
Correct |
48 ms |
39160 KB |
Output is correct |
| 6 |
Correct |
52 ms |
39416 KB |
Output is correct |
| 7 |
Correct |
47 ms |
39416 KB |
Output is correct |
| 8 |
Correct |
46 ms |
39416 KB |
Output is correct |
| 9 |
Correct |
49 ms |
39032 KB |
Output is correct |
| 10 |
Correct |
46 ms |
38008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
643 ms |
43260 KB |
Output is correct |
| 2 |
Correct |
619 ms |
48636 KB |
Output is correct |
| 3 |
Correct |
483 ms |
50588 KB |
Output is correct |
| 4 |
Correct |
445 ms |
49924 KB |
Output is correct |
| 5 |
Correct |
500 ms |
50720 KB |
Output is correct |
| 6 |
Correct |
573 ms |
47608 KB |
Output is correct |
| 7 |
Correct |
389 ms |
51300 KB |
Output is correct |
| 8 |
Correct |
304 ms |
48648 KB |
Output is correct |
| 9 |
Correct |
721 ms |
49912 KB |
Output is correct |
| 10 |
Correct |
680 ms |
49332 KB |
Output is correct |
