oj.uz

Submission #659144

# Submission time Handle Problem Language Result Execution time Memory
659144 2022-11-16T19:04:05 Z activedeltorre Strange Device (APIO19_strange_device) C++14
25 / 100
 2062 ms 156880 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;
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

strange_device.cpp: In function 'int main()':
strange_device.cpp:96: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]
   96 |     for(z=0; z<complete.size(); z++)
      |              ~^~~~~~~~~~~~~~~~
strange_device.cpp:122: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]
  122 |             while(index2+1<complete.size() && maxim>=complete[index2+1].first)
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:32:21: warning: unused variable 'm' [-Wunused-variable]
   32 |     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:32:23: warning: unused variable 'k' [-Wunused-variable]
   32 |     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:32:25: warning: unused variable 'l' [-Wunused-variable]
   32 |     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:32:81: warning: unused variable 'rest3' [-Wunused-variable]
   32 |     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:32:87: warning: unused variable 'rest4' [-Wunused-variable]
   32 |     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 38 ms 47716 KB Output is correct
3 Correct 40 ms 47672 KB Output is correct
4 Incorrect 23 ms 47188 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 47176 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 22 ms 47188 KB Output is correct
4 Correct 25 ms 47168 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Incorrect 26 ms 47416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47268 KB Output is correct
2 Incorrect 1935 ms 156880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47268 KB Output is correct
2 Incorrect 1935 ms 156880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47268 KB Output is correct
2 Incorrect 1935 ms 156880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47144 KB Output is correct
2 Correct 159 ms 50824 KB Output is correct
3 Correct 193 ms 50720 KB Output is correct
4 Correct 2062 ms 126336 KB Output is correct
5 Correct 179 ms 51612 KB Output is correct
6 Correct 184 ms 51424 KB Output is correct
7 Correct 188 ms 51608 KB Output is correct
8 Correct 193 ms 53416 KB Output is correct
9 Correct 195 ms 53560 KB Output is correct
10 Correct 157 ms 50488 KB Output is correct
11 Correct 155 ms 50560 KB Output is correct
12 Correct 155 ms 50660 KB Output is correct
13 Correct 193 ms 52492 KB Output is correct
14 Correct 1390 ms 79240 KB Output is correct
15 Correct 155 ms 51276 KB Output is correct
16 Correct 1399 ms 79620 KB Output is correct
17 Correct 1875 ms 121752 KB Output is correct
18 Correct 23 ms 47248 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 38 ms 47716 KB Output is correct
3 Correct 40 ms 47672 KB Output is correct
4 Incorrect 23 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -