oj.uz

답안 #659143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659143 2022-11-16T19:03:04 Z activedeltorre 이상한 기계 (APIO19_strange_device) C++14
20 / 100
 2102 ms 156948 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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47208 KB Output is correct
2 Correct 38 ms 47736 KB Output is correct
3 Correct 37 ms 48084 KB Output is correct
4 Incorrect 28 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 47192 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 22 ms 47248 KB Output is correct
4 Incorrect 26 ms 47268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47160 KB Output is correct
2 Incorrect 31 ms 47380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47184 KB Output is correct
2 Incorrect 1913 ms 156948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47184 KB Output is correct
2 Incorrect 1913 ms 156948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47184 KB Output is correct
2 Incorrect 1913 ms 156948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 164 ms 50784 KB Output is correct
3 Correct 198 ms 53992 KB Output is correct
4 Correct 2102 ms 126424 KB Output is correct
5 Correct 192 ms 54936 KB Output is correct
6 Correct 187 ms 54728 KB Output is correct
7 Correct 186 ms 54840 KB Output is correct
8 Correct 197 ms 56736 KB Output is correct
9 Correct 193 ms 56872 KB Output is correct
10 Correct 178 ms 53780 KB Output is correct
11 Correct 165 ms 53876 KB Output is correct
12 Correct 156 ms 54004 KB Output is correct
13 Correct 191 ms 55800 KB Output is correct
14 Correct 1397 ms 79356 KB Output is correct
15 Correct 163 ms 54516 KB Output is correct
16 Correct 1394 ms 79888 KB Output is correct
17 Correct 1818 ms 121920 KB Output is correct
18 Correct 22 ms 47188 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47208 KB Output is correct
2 Correct 38 ms 47736 KB Output is correct
3 Correct 37 ms 48084 KB Output is correct
4 Incorrect 28 ms 47188 KB Output isn't correct
5 Halted 0 ms 0 KB -