답안 #985059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
985059	2024-05-17T10:08:29 Z	SyedSohaib_123	이상한 기계 (APIO19_strange_device)	C++17	30 / 100	1128 ms	33700 KB

strange_device

#include<bits/stdc++.h>
 
 
 
using namespace std;
 
 
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
 
 
 
#define str string
#define append push_back
#define vector deque
#define vi vector<int>
#define int long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define endl '\n'
#define all(ls) ls.begin(),ls.end()
#define sorted(ls) sort(ls.begin(),ls.end());
#define reversed(ls) reverse(ls.begin(),ls.end());
#define print(n) for(auto i:n)cout<<i<<' ';cout<<endl;
#define input(n,ls,m) deque<n>ls(m);for(int i=0;i<m;i++)cin>>ls[i];
#define len(s) s.size()
#define ff first
#define ss second
#define N (int const) 3e5+1
#define pii pair<int,int>
#define SQ(x) ((x)*(x))
#define float double
 
 
int mod=1e9+7;
int mod1=998244353;
 
 
 
int sum_(vector<int>ls){int s=0;for(auto i:ls){s+=i;}return s;}
int min(int a,int b){if (a>b){return b;}return a;}
int max(int a,int b){if (a<b){return b;}return a;}
 
 
 
//......................................tHe ReaL cOdE beGinS HerE....................................../



int solve2(vector<pii> ls,int a,int b){
    map<pair<int,int>,bool>m;
    for(auto i:ls){
        for(int j=i.ff;j<=i.ss;j++){
            m[{(j+j/b)%a,j%b}]=1;
        }
    }
    return len(m);
}


 
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    vector<pii>ls;
    int cnt=0;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        cnt+=y-x+1;
        ls.append({x,y});
    }
    if(cnt<=1e6){cout<<solve2(ls,a,b)<<endl;return;}
    a/=gcd(a,b+1);
    a*=b;
    for(auto i:ls){
        if(i.ss-i.ff+1>=a){
            cout<<a<<endl;return;
        }
    }
    vector<pii>q;
    for(auto i:ls){
        int f=i.ff%a,s=i.ss%a;
        if(f<s or i.ff==i.ss) q.append({f,s});
        else{
            q.append({f,a-1});
            q.append({0,s});
        }
    }
    sorted(q);
    int ans=a-q[0].ff;
    int maxi=q[0].ss;
    for(int i=1;i<q.size();i++){
        if(q[i-1].ss<q[i].ff){
            ans-=q[i].ff-q[i-1].ss-1;
        }
        maxi=max(maxi,q[i].ss);
    }
    if(q[0].ff==maxi){
        for(auto i:q){
            if(i.ss!=q[0].ff){
                cout<<ans<<endl;return;
            }
        }
    }
    cout<<ans-(a-maxi-1)<<endl;
}
 
 
 
 
 
signed main(){
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:95:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=1;i<q.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	48 ms	12636 KB	Output is correct
3	Correct	68 ms	18260 KB	Output is correct
4	Correct	2 ms	856 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	7 ms	1320 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	35 ms	7004 KB	Output is correct
16	Correct	29 ms	7004 KB	Output is correct
17	Correct	121 ms	9812 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	600 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	122 ms	32312 KB	Output is correct
3	Correct	171 ms	32196 KB	Output is correct
4	Correct	116 ms	30532 KB	Output is correct
5	Correct	757 ms	33076 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1057 ms	33228 KB	Output is correct
3	Correct	1022 ms	33088 KB	Output is correct
4	Correct	1033 ms	33348 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1057 ms	33228 KB	Output is correct
3	Correct	1022 ms	33088 KB	Output is correct
4	Correct	1033 ms	33348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1080 ms	33208 KB	Output is correct
7	Correct	1029 ms	33700 KB	Output is correct
8	Correct	1047 ms	33416 KB	Output is correct
9	Correct	1128 ms	33076 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1057 ms	33228 KB	Output is correct
3	Correct	1022 ms	33088 KB	Output is correct
4	Correct	1033 ms	33348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	104 ms	3580 KB	Output is correct
7	Correct	105 ms	3708 KB	Output is correct
8	Correct	100 ms	3632 KB	Output is correct
9	Correct	105 ms	3652 KB	Output is correct
10	Correct	114 ms	3668 KB	Output is correct
11	Correct	101 ms	3668 KB	Output is correct
12	Correct	101 ms	3476 KB	Output is correct
13	Correct	103 ms	3668 KB	Output is correct
14	Correct	106 ms	3664 KB	Output is correct
15	Incorrect	109 ms	3692 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	120 ms	3576 KB	Output is correct
3	Correct	114 ms	3544 KB	Output is correct
4	Correct	1121 ms	33216 KB	Output is correct
5	Correct	105 ms	3536 KB	Output is correct
6	Correct	106 ms	3664 KB	Output is correct
7	Correct	116 ms	3700 KB	Output is correct
8	Correct	120 ms	3700 KB	Output is correct
9	Correct	104 ms	3668 KB	Output is correct
10	Correct	107 ms	3544 KB	Output is correct
11	Correct	118 ms	3756 KB	Output is correct
12	Correct	99 ms	3644 KB	Output is correct
13	Correct	106 ms	3704 KB	Output is correct
14	Incorrect	1092 ms	33224 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	48 ms	12636 KB	Output is correct
3	Correct	68 ms	18260 KB	Output is correct
4	Correct	2 ms	856 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	7 ms	1320 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	35 ms	7004 KB	Output is correct
16	Correct	29 ms	7004 KB	Output is correct
17	Correct	121 ms	9812 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	600 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	122 ms	32312 KB	Output is correct
26	Correct	171 ms	32196 KB	Output is correct
27	Correct	116 ms	30532 KB	Output is correct
28	Correct	757 ms	33076 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1057 ms	33228 KB	Output is correct
31	Correct	1022 ms	33088 KB	Output is correct
32	Correct	1033 ms	33348 KB	Output is correct
33	Correct	1 ms	344 KB	Output is correct
34	Correct	1080 ms	33208 KB	Output is correct
35	Correct	1029 ms	33700 KB	Output is correct
36	Correct	1047 ms	33416 KB	Output is correct
37	Correct	1128 ms	33076 KB	Output is correct
38	Correct	0 ms	344 KB	Output is correct
39	Correct	104 ms	3580 KB	Output is correct
40	Correct	105 ms	3708 KB	Output is correct
41	Correct	100 ms	3632 KB	Output is correct
42	Correct	105 ms	3652 KB	Output is correct
43	Correct	114 ms	3668 KB	Output is correct
44	Correct	101 ms	3668 KB	Output is correct
45	Correct	101 ms	3476 KB	Output is correct
46	Correct	103 ms	3668 KB	Output is correct
47	Correct	106 ms	3664 KB	Output is correct
48	Incorrect	109 ms	3692 KB	Output isn't correct
49	Halted	0 ms	0 KB	-