Submission #659163

#	Time	Username	Problem	Language	Result	Execution time	Memory
659163		activedeltorre	이상한 기계 (APIO19_strange_device)	C++14	40 / 100	2035 ms	66264 KiB

strange_device

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
map<long long,long long>norm;
vector<pair<long long,long long> >vec;
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});
                vec.push_back({((val1+1)%a)*b,(val2)%a*b-1});
            }
            else if(val4==val3+1)
            {
                //complete.push_back({(val1+1)%a,a-1});
                vec.push_back({((val1+1)%a)*b,a*b-1});
                //complete.push_back({0,(val2-1)%a});
                vec.push_back({0,(val2)%a*b-1});
            }
            else
            {
                vec.push_back({0,a*b-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});
            vec.push_back({((val1)%a)*b+rest1,((val1)%a)*b+rest2});
        }
        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. ;
            vec.push_back({(val1%a)*b+rest1,((val1)%a)*b+b-1});
            vec.push_back({(val2%a)*b,((val2)%a)*b+rest2});
        }
    }
    sort(vec.begin(),vec.end(),cmp);
    long long nr=vec.size(),index,st,dr,suma=0;
    for(j=0; j<nr; j++)
    {
        index=j;
        st=vec[j].first;
        dr=vec[j].second;
        while(index+1<nr && dr>=vec[index+1].first)
        {
            dr=max(dr,vec[index+1].second);
            index++;
        }
        suma=suma+dr-st+1;
        j=index;
    }
    cout<<suma;
    /* 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==-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;
                 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!=-1)
         {
             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;
         }
     }*/
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
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:53: warning: unused variable 'valoare' [-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:61: warning: unused variable 'cnt' [-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;
      |                                                                                       ^~~~~
strange_device.cpp:35:93: warning: unused variable 'z' [-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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30