oj.uz

답안 #659152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659152 2022-11-16T19:26:24 Z activedeltorre 이상한 기계 (APIO19_strange_device) C++14
40 / 100
 3102 ms 319232 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=1e17;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 36 ms 47700 KB Output is correct
3 Correct 37 ms 47700 KB Output is correct
4 Incorrect 23 ms 47180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47244 KB Output is correct
2 Correct 26 ms 47188 KB Output is correct
3 Correct 24 ms 47176 KB Output is correct
4 Correct 24 ms 47260 KB Output is correct
5 Correct 22 ms 47148 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47188 KB Output is correct
2 Correct 30 ms 47444 KB Output is correct
3 Correct 29 ms 47316 KB Output is correct
4 Correct 31 ms 47400 KB Output is correct
5 Correct 1367 ms 174528 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47152 KB Output is correct
2 Correct 1954 ms 156892 KB Output is correct
3 Correct 3102 ms 319232 KB Output is correct
4 Correct 3069 ms 316824 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47152 KB Output is correct
2 Correct 1954 ms 156892 KB Output is correct
3 Correct 3102 ms 319232 KB Output is correct
4 Correct 3069 ms 316824 KB Output is correct
5 Correct 25 ms 47244 KB Output is correct
6 Correct 2674 ms 240972 KB Output is correct
7 Correct 1646 ms 147280 KB Output is correct
8 Correct 2462 ms 239516 KB Output is correct
9 Correct 2947 ms 239552 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47152 KB Output is correct
2 Correct 1954 ms 156892 KB Output is correct
3 Correct 3102 ms 319232 KB Output is correct
4 Correct 3069 ms 316824 KB Output is correct
5 Correct 27 ms 47384 KB Output is correct
6 Correct 228 ms 65088 KB Output is correct
7 Correct 261 ms 68524 KB Output is correct
8 Correct 255 ms 68400 KB Output is correct
9 Correct 259 ms 68452 KB Output is correct
10 Correct 216 ms 62512 KB Output is correct
11 Incorrect 244 ms 68452 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 47252 KB Output is correct
2 Correct 160 ms 51048 KB Output is correct
3 Correct 172 ms 51208 KB Output is correct
4 Correct 2025 ms 126460 KB Output is correct
5 Correct 185 ms 52068 KB Output is correct
6 Correct 178 ms 51840 KB Output is correct
7 Correct 189 ms 52024 KB Output is correct
8 Correct 223 ms 53908 KB Output is correct
9 Correct 193 ms 54088 KB Output is correct
10 Correct 180 ms 50992 KB Output is correct
11 Correct 167 ms 51116 KB Output is correct
12 Correct 165 ms 51112 KB Output is correct
13 Correct 197 ms 52996 KB Output is correct
14 Correct 1454 ms 79436 KB Output is correct
15 Correct 160 ms 51776 KB Output is correct
16 Correct 1350 ms 79896 KB Output is correct
17 Correct 1776 ms 122052 KB Output is correct
18 Correct 27 ms 47188 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 36 ms 47700 KB Output is correct
3 Correct 37 ms 47700 KB Output is correct
4 Incorrect 23 ms 47180 KB Output isn't correct
5 Halted 0 ms 0 KB -