| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 659152 | 2022-11-16T19:26:24 Z | activedeltorre | Strange Device (APIO19_strange_device) | C++14 | 3102 ms | 319232 KB |
#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;
long long inf=1e17;
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;
}
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,inf});
}
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,inf});
///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,inf});
}
}
sort(complete.begin(),complete.end(),cmp2);
long long suma=0,nr,dr,index,maxim=-1,index2,lft,rgh,st;
for(z=0; z<complete.size(); z++)
{
lft=complete[z].first;
rgh=complete[z].second;
if(rgh==inf && (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;
st=vec[i][j].first;
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-st+1;
j=index;
}
}
else if(rgh!=inf)
{
index2=z;
maxim=rgh;
while(index2+1<complete.size() && maxim>=complete[index2+1].first)
{
if(complete[index2+1].second!=inf)
{
maxim=max(maxim,complete[index2+1].second);
}
index2++;
}
suma=suma+(maxim-lft+1)*(b);
z=index2;
}
}
cout<<suma;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 47188 KB | Output is correct |
| 2 | Correct | 36 ms | 47700 KB | Output is correct |
| 3 | Correct | 37 ms | 47700 KB | Output is correct |
| 4 | Incorrect | 23 ms | 47180 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 47244 KB | Output is correct |
| 2 | Correct | 26 ms | 47188 KB | Output is correct |
| 3 | Correct | 24 ms | 47176 KB | Output is correct |
| 4 | Correct | 24 ms | 47260 KB | Output is correct |
| 5 | Correct | 22 ms | 47148 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 47188 KB | Output is correct |
| 2 | Correct | 30 ms | 47444 KB | Output is correct |
| 3 | Correct | 29 ms | 47316 KB | Output is correct |
| 4 | Correct | 31 ms | 47400 KB | Output is correct |
| 5 | Correct | 1367 ms | 174528 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 47152 KB | Output is correct |
| 2 | Correct | 1954 ms | 156892 KB | Output is correct |
| 3 | Correct | 3102 ms | 319232 KB | Output is correct |
| 4 | Correct | 3069 ms | 316824 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 47152 KB | Output is correct |
| 2 | Correct | 1954 ms | 156892 KB | Output is correct |
| 3 | Correct | 3102 ms | 319232 KB | Output is correct |
| 4 | Correct | 3069 ms | 316824 KB | Output is correct |
| 5 | Correct | 25 ms | 47244 KB | Output is correct |
| 6 | Correct | 2674 ms | 240972 KB | Output is correct |
| 7 | Correct | 1646 ms | 147280 KB | Output is correct |
| 8 | Correct | 2462 ms | 239516 KB | Output is correct |
| 9 | Correct | 2947 ms | 239552 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 47152 KB | Output is correct |
| 2 | Correct | 1954 ms | 156892 KB | Output is correct |
| 3 | Correct | 3102 ms | 319232 KB | Output is correct |
| 4 | Correct | 3069 ms | 316824 KB | Output is correct |
| 5 | Correct | 27 ms | 47384 KB | Output is correct |
| 6 | Correct | 228 ms | 65088 KB | Output is correct |
| 7 | Correct | 261 ms | 68524 KB | Output is correct |
| 8 | Correct | 255 ms | 68400 KB | Output is correct |
| 9 | Correct | 259 ms | 68452 KB | Output is correct |
| 10 | Correct | 216 ms | 62512 KB | Output is correct |
| 11 | Incorrect | 244 ms | 68452 KB | Output isn't correct |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 26 ms | 47252 KB | Output is correct |
| 2 | Correct | 160 ms | 51048 KB | Output is correct |
| 3 | Correct | 172 ms | 51208 KB | Output is correct |
| 4 | Correct | 2025 ms | 126460 KB | Output is correct |
| 5 | Correct | 185 ms | 52068 KB | Output is correct |
| 6 | Correct | 178 ms | 51840 KB | Output is correct |
| 7 | Correct | 189 ms | 52024 KB | Output is correct |
| 8 | Correct | 223 ms | 53908 KB | Output is correct |
| 9 | Correct | 193 ms | 54088 KB | Output is correct |
| 10 | Correct | 180 ms | 50992 KB | Output is correct |
| 11 | Correct | 167 ms | 51116 KB | Output is correct |
| 12 | Correct | 165 ms | 51112 KB | Output is correct |
| 13 | Correct | 197 ms | 52996 KB | Output is correct |
| 14 | Correct | 1454 ms | 79436 KB | Output is correct |
| 15 | Correct | 160 ms | 51776 KB | Output is correct |
| 16 | Correct | 1350 ms | 79896 KB | Output is correct |
| 17 | Correct | 1776 ms | 122052 KB | Output is correct |
| 18 | Correct | 27 ms | 47188 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 47188 KB | Output is correct |
| 2 | Correct | 36 ms | 47700 KB | Output is correct |
| 3 | Correct | 37 ms | 47700 KB | Output is correct |
| 4 | Incorrect | 23 ms | 47180 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |