| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56974 |
2018-07-13T11:33:07 Z |
babo |
None (JOI15_walls) |
C++14 |
|
760 ms |
34816 KB |
#include <bits/stdc++.h>
#define L long long
using namespace std;
L n,m,lensum;
struct Wall{
L s,e,len,ord,ans;
}a[200020];
bool operator<(Wall a,Wall b){
return a.len<b.len;
}
bool cmp(Wall a,Wall b){
return a.ord<b.ord;
}
L lazor[200020];
vector<L>lazors;
struct Line{
L s,e,det,ord,len;
};
bool operator<(Line a,Line b){
return a.len<b.len;
}
bool operator==(Line a,Line b){
return a.s==b.s&&a.len==b.len&&a.e==b.e&&a.ord==b.ord;
}
struct Line2{
L s,e,det,ord,len;
void copy(Line temp){
s=temp.s;
e=temp.e;
det=temp.det;
ord=temp.ord;
len=temp.len;
}
};
bool operator<(Line2 a,Line2 b){
return a.ord<b.ord;
}
bool operator==(Line2 a,Line2 b){
return a.s==b.s&&a.len==b.len&&a.e==b.e&&a.ord==b.ord;
}
set<Line>st;
set<Line2>st2;
vector<Line>lines;
void do1(){
L i;
for(i=1;i<=n;i++)
{
L ansans=0;
if(a[i].s>lazor[1]) ansans=a[i].s-lazor[1];
else if(a[i].e<lazor[1]) ansans=lazor[1]-a[i].e;
else ansans=0;
printf("%lld ",ansans);
}
exit(0);
}
L ab(L x){
return x>0?x:-x;
}
int main()
{
scanf("%lld %lld",&n,&m);
L i;
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i].s,&a[i].e);
a[i].len=a[i].e-a[i].s;
a[i].ord=i;
a[i].ans=0;
}
for(i=1;i<=m;i++)
{
scanf("%lld",&lazor[i]);
}
if(m==1)
{
do1();
return 0;
}
sort(a+1,a+n+1);
for(i=1;i<=m;i++)
{
if(lazors.size()&&i<m&&(lazor[i]-lazors[lazors.size()-1])*(lazor[i]-lazor[i+1])<0)
{
continue;
}
lazors.push_back(lazor[i]);
}
for(i=1;i<lazors.size();i++)
{
Line temp;
temp.s=lazors[i-1];
temp.e=lazors[i];
temp.det=temp.s<temp.e;
temp.len=temp.e-temp.s;
if(temp.len<0) temp.len*=-1;
lensum+=temp.len;
temp.ord=i;
lines.push_back(temp);
Line2 temp2;
temp2.copy(temp);
st.insert(temp);
st2.insert(temp2);
}
//printf("lensum %lld\n",lensum);
for(i=1;i<=n;i++)
{
while(1)
{
set<Line>::iterator it=st.begin();
if(it==st.end()) break;
if(it->len<=a[i].len)
{
//puts("1");
Line2 temp;
temp.ord=it->ord;
st.erase(it);
set<Line2>::iterator it2=st2.lower_bound(temp);
if(it2==st2.begin())
{
set<Line2>::iterator it3=it2;
it3++;
if(it3==st2.end()) continue;
Line2 out2=*it2;
Line out;
out.s=out2.s;
out.e=out2.e;
out.ord=out2.ord;
out.det=out2.det;
out.len=out2.len;
lensum-=out.len;
st.erase(out);
st2.erase(out2);
continue;
}
else
{
set<Line2>::iterator it3=it2;
it3++;
if(it3==st2.end())
{
Line2 out2=*it2;
Line out;
out.s=out2.s;
out.e=out2.e;
out.ord=out2.ord;
out.det=out2.det;
out.len=out2.len;
lensum-=out.len;
st.erase(out);
st2.erase(out2);
continue;
}
}
Line2 now2=*it2;
it2++;
Line2 next2=*it2;
it2--;
it2--;
Line2 prev2=*it2;
Line now;
now.s=now2.s;
now.e=now2.e;
now.det=now2.det;
now.len=now2.len;
now.ord=now2.ord;
Line next;
next.s=next2.s;
next.e=next2.e;
next.det=next2.det;
next.len=next2.len;
next.ord=next2.ord;
Line prev;
prev.s=prev2.s;
prev.e=prev2.e;
prev.det=prev2.det;
prev.len=prev2.len;
prev.ord=prev2.ord;
st.erase(now);
st.erase(next);
st.erase(prev);
st2.erase(now2);
st2.erase(next2);
st2.erase(prev2);
//printf("********%lld %lld\n",lensum,now.len);
lensum-=2*now.len;
if(now.det==1)
{
Line input;
input.s=prev.s;
input.e=next.e;
input.len=input.s-input.e;
input.det=0;
input.ord=now.ord;
Line2 input2;
input2.copy(input);
st.insert(input);
st2.insert(input2);
}
else
{
Line input;
input.s=prev.s;
input.e=next.e;
input.len=input.e-input.s;
input.det=1;
input.ord=now.ord;
Line2 input2;
input2.copy(input);
st.insert(input);
st2.insert(input2);
}
}
else break;
}
/*puts("");
set<Line2>::iterator itit;
for(itit=st2.begin();itit!=st2.end();itit++)
printf("%lld %lld %lld\n",itit->s,itit->e,itit->det);
puts("");*/
//printf("%lld\n",lensum);
set<Line2>::iterator it=st2.begin();
if(it->det==1) a[i].ans=ab((it->s)-a[i].s);
else a[i].ans=ab((it->s)-a[i].e);
//printf("%lld %lld ",a[i].ord,a[i].ans);
a[i].ans+=lensum-(st2.size())*a[i].len;
//printf("%lld\n",a[i].ans);
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)
{
printf("%lld\n",a[i].ans);
}
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:106:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1;i<lazors.size();i++)
~^~~~~~~~~~~~~~
walls.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&n,&m);
~~~~~^~~~~~~~~~~~~~~~~~~
walls.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&a[i].s,&a[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&lazor[i]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1744 KB |
Output is correct |
| 2 |
Incorrect |
575 ms |
33992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
33992 KB |
Output is correct |
| 2 |
Incorrect |
760 ms |
34816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1744 KB |
Output is correct |
| 2 |
Incorrect |
575 ms |
33992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
