제출 #197754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197754		Ruxandra985	이상한 기계 (APIO19_strange_device)	C++14	25 / 100	834 ms	44176 KiB

strange_device

#include <bits/stdc++.h>
#define DIMN 5000010
using namespace std;
pair <long long,int> v[DIMN];
map <pair <long long , long long> , long long> mp;
int cmmdc (int x , int y){
    int r;
    while (y){
        r = x % y;
        x = y;
        y = r;
    }
    return x;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , over , elem , i , into;
    long long a , b, l , r , sol;
    fscanf (fin,"%d%lld%lld",&n,&a,&b);
    a /= cmmdc (a , b + 1);
    over = 0;
    if ( a > 1000000000000000000LL / b )
        over = 1;
    elem = 0;
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld%lld",&l,&r);
        if (over){
            /// dau resturile l si r
            v[++elem] = make_pair( l , 1 ); /// begin
            v[++elem] = make_pair( r + 1 , 0 ); /// end
        }
        else {
            if (r - l + 1 >= a * b){ /// sunt toate resturile
                v[++elem] = make_pair( 0 , 1 ); /// begin
                v[++elem] = make_pair( a * b , 0 ); /// end
            }
            else {
                l = l % (a * b);
                r = r % (a * b);

                if (l <= r){
                    v[++elem] = make_pair( l , 1 ); /// begin
                    v[++elem] = make_pair( r + 1 , 0 ); /// end
                }
                else { /// se duce l ..  ab - 1 0 ... r
                    v[++elem] = make_pair( l , 1 ); /// begin
                    v[++elem] = make_pair( a * b , 0 ); /// end
                    v[++elem] = make_pair( 0 , 1 ); /// begin
                    v[++elem] = make_pair( r + 1 , 0 ); /// end
                }

            }

        }
    }

    /*for (long long j = 0; j < a * b ; j++){
        if( mp[make_pair((j + j / b) % a , j % b)]){
            fprintf (fout,"%lld\n",mp[make_pair((j + j / b) % a , j % b)] - j);
            break;
        }
        mp[make_pair((j + j / b) % a , j % b)] = j;
    }*/
    /// acum eu am un vector de evenimente , vr sa vad reunuiunea
    sol = 0;

    sort (v + 1 , v + elem + 1);
    into = 0;
    for ( i = 1 ; i <= elem ; i++ ){

        while (i < elem && v[i].first == v[i+1].first){
            if (v[i].second == 1)
                into++;
            else into--;
            i++;
        }
        if (i == elem)
            break;
        if (v[i].second == 1)
            into++;
        else into--;
        if (into > 0){
            sol = sol + v[i+1].first - v[i].first;
        }
    }
    fprintf (fout,"%lld",sol);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

strange_device.cpp: In function 'int main()':
strange_device.cpp:22:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%lld%lld",&n,&a,&b);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:29:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&l,&r);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30