oj.uz

Submission #659157

# Submission time Handle Problem Language Result Execution time Memory
659157 2022-11-16T19:30:35 Z activedeltorre Strange Device (APIO19_strange_device) C++14
40 / 100
 3000 ms 282256 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=1e18;
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;
}
long long gcd(long long a , long  b)
{
   if(b==0) return a;
   a%=b;
   return gcd(b,a);
}
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

strange_device.cpp: In function 'int main()':
strange_device.cpp:98:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(z=0; z<complete.size(); z++)
      |              ~^~~~~~~~~~~~~~~~
strange_device.cpp:125:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             while(index2+1<complete.size() && maxim>=complete[index2+1].first)
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:35:21: warning: unused variable 'm' [-Wunused-variable]
   35 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
      |                     ^
strange_device.cpp:35:23: warning: unused variable 'k' [-Wunused-variable]
   35 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
      |                       ^
strange_device.cpp:35:25: warning: unused variable 'l' [-Wunused-variable]
   35 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
      |                         ^
strange_device.cpp:35:81: warning: unused variable 'rest3' [-Wunused-variable]
   35 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
      |                                                                                 ^~~~~
strange_device.cpp:35:87: warning: unused variable 'rest4' [-Wunused-variable]
   35 |     long long n,i,j,m,k,l,a,b,val1,val2,rest1,rest2,valoare,cnt=0,x,y,val3,val4,rest3,rest4,z;
      |                                                                                       ^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 37 ms 47944 KB Output is correct
3 Correct 37 ms 47884 KB Output is correct
4 Incorrect 24 ms 47244 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 25 ms 47344 KB Output is correct
3 Correct 26 ms 47188 KB Output is correct
4 Correct 25 ms 47160 KB Output is correct
5 Correct 24 ms 47240 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47144 KB Output is correct
2 Correct 26 ms 47380 KB Output is correct
3 Correct 25 ms 47252 KB Output is correct
4 Correct 27 ms 47396 KB Output is correct
5 Correct 1276 ms 157016 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 1865 ms 156908 KB Output is correct
3 Correct 2973 ms 282256 KB Output is correct
4 Correct 3000 ms 282156 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 1865 ms 156908 KB Output is correct
3 Correct 2973 ms 282256 KB Output is correct
4 Correct 3000 ms 282156 KB Output is correct
5 Correct 22 ms 47188 KB Output is correct
6 Correct 2561 ms 203900 KB Output is correct
7 Correct 1607 ms 110032 KB Output is correct
8 Correct 2404 ms 203892 KB Output is correct
9 Correct 2873 ms 203864 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 1865 ms 156908 KB Output is correct
3 Correct 2973 ms 282256 KB Output is correct
4 Correct 3000 ms 282156 KB Output is correct
5 Correct 22 ms 47212 KB Output is correct
6 Correct 236 ms 61408 KB Output is correct
7 Correct 242 ms 65204 KB Output is correct
8 Correct 238 ms 65164 KB Output is correct
9 Correct 238 ms 65184 KB Output is correct
10 Correct 206 ms 59004 KB Output is correct
11 Incorrect 229 ms 65088 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47296 KB Output is correct
2 Correct 154 ms 50880 KB Output is correct
3 Correct 172 ms 50764 KB Output is correct
4 Correct 1966 ms 126416 KB Output is correct
5 Correct 177 ms 51704 KB Output is correct
6 Correct 173 ms 51564 KB Output is correct
7 Correct 179 ms 51688 KB Output is correct
8 Correct 191 ms 53480 KB Output is correct
9 Correct 184 ms 53696 KB Output is correct
10 Correct 157 ms 50584 KB Output is correct
11 Correct 171 ms 50752 KB Output is correct
12 Correct 152 ms 50768 KB Output is correct
13 Correct 182 ms 52624 KB Output is correct
14 Correct 1347 ms 79260 KB Output is correct
15 Correct 151 ms 51400 KB Output is correct
16 Correct 1312 ms 79840 KB Output is correct
17 Correct 1727 ms 122188 KB Output is correct
18 Correct 25 ms 47164 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 37 ms 47944 KB Output is correct
3 Correct 37 ms 47884 KB Output is correct
4 Incorrect 24 ms 47244 KB Output isn't correct
5 Halted 0 ms 0 KB -