| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123045 |
2019-06-30T05:48:11 Z |
ansol4328 |
수족관 1 (KOI13_aqua1) |
C++11 |
|
12 ms |
3324 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;
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
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 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;
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);
}
}
printf("%lld",tot);
return 0;
}
Compilation message
aqua1.cpp: In function 'int main()':
aqua1.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua1.cpp:139: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:143: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:144: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:149: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&hn);
~~~~~^~~~~~~~~~
aqua1.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x1,&y1);
~~~~~^~~~~~~~~~~~~~~~~
aqua1.cpp:157: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 |
504 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 |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 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 |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 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 |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
420 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 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 |
9 ms |
3324 KB |
Output is correct |
| 2 |
Correct |
10 ms |
3192 KB |
Output is correct |
| 3 |
Correct |
10 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
10 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3268 KB |
Output is correct |
| 7 |
Correct |
9 ms |
3292 KB |
Output is correct |
| 8 |
Correct |
8 ms |
3192 KB |
Output is correct |
| 9 |
Correct |
10 ms |
3192 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3192 KB |
Output is correct |
