# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
659144 | activedeltorre | Strange Device (APIO19_strange_device) | C++14 | 2062 ms | 156880 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
map<long long,long long>norm;
vector<pair<long long,long long> >vec[2000005];
vector<pair<long long,long long > >complete;
bool cmp(pair<long long,long long> a,pair<long long,long long>b)
{
if(a.first!=b.first)
{
return a.first<b.first;
}
return a.second>b.second;
}
bool cmp2(pair<long long,long long> a,pair<long long,long long>b)
{
if(a.first!=b.first)
{
return a.first<b.first;
}
if(a.second==-1)
{
return a.second>b.second;
}
return a.second<b.second;
}
int main()
{
long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
cin>>n>>a>>b;
a=a/__gcd(a,b+1);
for(i=1; i<=n; i++)
{
cin>>x>>y;
val1=x/b;
val2=y/b;
rest1=x%b;
rest2=y%b;
if(val2-val1>=2)
{
val3=val1/a;
val4=val2/a;
if(val3==val4)
{
complete.push_back({(val1+1)%a,(val2-1)%a});
}
else if(val4==val3+1)
{
complete.push_back({(val1+1)%a,a-1});
complete.push_back({0,(val2-1)%a});
}
else
{
complete.push_back({0,a-1});
}
}
if(val1==val2)
{
valoare=(val1)%a;
if(norm[valoare]==0)
{
cnt++;
norm[valoare]=cnt;
}
vec[norm[valoare]].push_back({rest1,rest2});
complete.push_back({valoare,-1});
}
else
{
///adaug preim segmnt
valoare=(val1)%a;
if(norm[valoare]==0)
{
cnt++;
norm[valoare]=cnt;
}
vec[norm[valoare]].push_back({rest1,b-1});
complete.push_back({valoare,-1});
///adaug al doilea segmnt
valoare=(val2)%a;
if(norm[valoare]==0)
{
cnt++;
norm[valoare]=cnt;
}
vec[norm[valoare]].push_back({0,rest2});
complete.push_back({valoare,-1});
}
}
sort(complete.begin(),complete.end(),cmp2);
long long suma=0,nr,dr,index,maxim=-1,index2,lft,rgh;
for(z=0; z<complete.size(); z++)
{
lft=complete[z].first;
rgh=complete[z].second;
if(rgh==-1 && (z==0 ||complete[z-1].first!=lft))
{
i=norm[lft];
sort(vec[i].begin(),vec[i].end(),cmp);
nr=vec[i].size();
for(j=0; j<nr; j++)
{
index=j;
dr=vec[i][j].second;
while(index+1<nr && dr>=vec[i][index+1].first)
{
dr=max(dr,vec[i][index+1].second);
index++;
}
suma=suma+dr-vec[i][j].first+1;
j=index;
}
}
else if(rgh!=-1)
{
index2=z;
maxim=rgh;
while(index2+1<complete.size() && maxim>=complete[index2+1].first)
{
maxim=max(maxim,complete[index2+1].second);
index2++;
}
suma=suma+(maxim-lft+1)*(b);
z=index2;
}
}
cout<<suma;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |