oj.uz

Submission #659163

# Submission time Handle Problem Language Result Execution time Memory
659163 2022-11-16T20:13:59 Z activedeltorre Strange Device (APIO19_strange_device) C++14
40 / 100
 2035 ms 66264 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;
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 14 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1135 ms 66136 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2035 ms 16900 KB Output is correct
3 Correct 1827 ms 66264 KB Output is correct
4 Correct 1840 ms 66112 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2035 ms 16900 KB Output is correct
3 Correct 1827 ms 66264 KB Output is correct
4 Correct 1840 ms 66112 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2009 ms 66112 KB Output is correct
7 Correct 1409 ms 16956 KB Output is correct
8 Correct 1722 ms 66092 KB Output is correct
9 Correct 1939 ms 66104 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2035 ms 16900 KB Output is correct
3 Correct 1827 ms 66264 KB Output is correct
4 Correct 1840 ms 66112 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 155 ms 4492 KB Output is correct
7 Correct 182 ms 8568 KB Output is correct
8 Correct 162 ms 8624 KB Output is correct
9 Correct 182 ms 8588 KB Output is correct
10 Correct 140 ms 4408 KB Output is correct
11 Incorrect 162 ms 8520 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 0 ms 212 KB Output is correct
2 Correct 146 ms 2412 KB Output is correct
3 Correct 150 ms 2408 KB Output is correct
4 Correct 1573 ms 33328 KB Output is correct
5 Correct 133 ms 2404 KB Output is correct
6 Correct 135 ms 2356 KB Output is correct
7 Correct 136 ms 2420 KB Output is correct
8 Correct 173 ms 2416 KB Output is correct
9 Correct 137 ms 2368 KB Output is correct
10 Correct 131 ms 2380 KB Output is correct
11 Correct 135 ms 2404 KB Output is correct
12 Correct 129 ms 2488 KB Output is correct
13 Correct 136 ms 2456 KB Output is correct
14 Correct 1373 ms 16812 KB Output is correct
15 Correct 138 ms 2492 KB Output is correct
16 Correct 1292 ms 16784 KB Output is correct
17 Correct 1370 ms 33272 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 14 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -