oj.uz

Submission #659153

# Submission time Handle Problem Language Result Execution time Memory
659153 2022-11-16T19:27:41 Z activedeltorre Strange Device (APIO19_strange_device) C++14
40 / 100
 3029 ms 287280 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+1;
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

strange_device.cpp: In function 'int main()':
strange_device.cpp:92: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]
   92 |     for(z=0; z<complete.size(); z++)
      |              ~^~~~~~~~~~~~~~~~
strange_device.cpp:119: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]
  119 |             while(index2+1<complete.size() && maxim>=complete[index2+1].first)
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:29:21: warning: unused variable 'm' [-Wunused-variable]
   29 |     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:29:23: warning: unused variable 'k' [-Wunused-variable]
   29 |     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:29:25: warning: unused variable 'l' [-Wunused-variable]
   29 |     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:29:81: warning: unused variable 'rest3' [-Wunused-variable]
   29 |     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:29:87: warning: unused variable 'rest4' [-Wunused-variable]
   29 |     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 39 ms 47908 KB Output is correct
3 Correct 39 ms 47764 KB Output is correct
4 Incorrect 24 ms 47156 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 23 ms 47232 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 23 ms 47268 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47264 KB Output is correct
2 Correct 25 ms 47388 KB Output is correct
3 Correct 26 ms 47316 KB Output is correct
4 Correct 25 ms 47388 KB Output is correct
5 Correct 1224 ms 159920 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 1842 ms 156832 KB Output is correct
3 Correct 2953 ms 287280 KB Output is correct
4 Correct 3029 ms 287108 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 1842 ms 156832 KB Output is correct
3 Correct 2953 ms 287280 KB Output is correct
4 Correct 3029 ms 287108 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 2586 ms 207112 KB Output is correct
7 Correct 1643 ms 113192 KB Output is correct
8 Correct 2398 ms 206908 KB Output is correct
9 Correct 2855 ms 205228 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 1842 ms 156832 KB Output is correct
3 Correct 2953 ms 287280 KB Output is correct
4 Correct 3029 ms 287108 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 221 ms 61512 KB Output is correct
7 Correct 257 ms 65228 KB Output is correct
8 Correct 250 ms 65368 KB Output is correct
9 Correct 247 ms 65224 KB Output is correct
10 Correct 212 ms 59004 KB Output is correct
11 Incorrect 239 ms 65336 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 25 ms 47188 KB Output is correct
2 Correct 159 ms 51120 KB Output is correct
3 Correct 174 ms 50872 KB Output is correct
4 Correct 2009 ms 126492 KB Output is correct
5 Correct 185 ms 51896 KB Output is correct
6 Correct 181 ms 51616 KB Output is correct
7 Correct 179 ms 51888 KB Output is correct
8 Correct 190 ms 53664 KB Output is correct
9 Correct 183 ms 53836 KB Output is correct
10 Correct 163 ms 50740 KB Output is correct
11 Correct 158 ms 50796 KB Output is correct
12 Correct 154 ms 50928 KB Output is correct
13 Correct 180 ms 52740 KB Output is correct
14 Correct 1318 ms 79416 KB Output is correct
15 Correct 154 ms 51512 KB Output is correct
16 Correct 1325 ms 79904 KB Output is correct
17 Correct 1782 ms 121968 KB Output is correct
18 Correct 24 ms 47188 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 39 ms 47908 KB Output is correct
3 Correct 39 ms 47764 KB Output is correct
4 Incorrect 24 ms 47156 KB Output isn't correct
5 Halted 0 ms 0 KB -