| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123032 |
2019-06-30T05:05:49 Z |
ansol4328 |
수족관 2 (KOI13_aqua2) |
C++11 |
|
463 ms |
40952 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;
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);
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];
}
};
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, prevh=0;
while(idx<=c)
{
ll leak=0;
ll gap=line[idx].height-prevh;
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);
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-1)*gap;
leak+=block;
double val=(double)block/hole_num;
T.add_time(val,l,r-1);
}
}
idx++;
}while(line[idx].height==line[idx-1].height);
prevh=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:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua2.cpp:131: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:135: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:136: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:141: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:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&hn);
~~~~~^~~~~~~~~~
aqua2.cpp:148: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:149: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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
31100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
463 ms |
40952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
