oj.uz

Submission #984865

# Submission time Handle Problem Language Result Execution time Memory
984865 2024-05-17T07:34:56 Z SyedSohaib_123 Strange Device (APIO19_strange_device) C++17
10 / 100
 1128 ms 68380 KB 
#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....................................../



 
void solve(){
    int n,a,b;;
    cin>>n>>a>>b;
    vector<pii>ls;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        ls.append({x,y});
    }
    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=0;
    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);
    }
    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:81: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]
   81 |     for(int i=1;i<q.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 10 ms 584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1058 ms 32976 KB Output is correct
3 Correct 1076 ms 33464 KB Output is correct
4 Correct 1075 ms 68308 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1058 ms 32976 KB Output is correct
3 Correct 1076 ms 33464 KB Output is correct
4 Correct 1075 ms 68308 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1029 ms 68300 KB Output is correct
7 Correct 1072 ms 68156 KB Output is correct
8 Correct 1010 ms 68364 KB Output is correct
9 Correct 1125 ms 68224 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1058 ms 32976 KB Output is correct
3 Correct 1076 ms 33464 KB Output is correct
4 Correct 1075 ms 68308 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 100 ms 7352 KB Output is correct
7 Correct 117 ms 7248 KB Output is correct
8 Correct 101 ms 7276 KB Output is correct
9 Correct 121 ms 7316 KB Output is correct
10 Correct 99 ms 7352 KB Output is correct
11 Correct 102 ms 7252 KB Output is correct
12 Correct 103 ms 7248 KB Output is correct
13 Correct 105 ms 7280 KB Output is correct
14 Correct 102 ms 7216 KB Output is correct
15 Incorrect 107 ms 7248 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 125 ms 3596 KB Output is correct
3 Correct 106 ms 7540 KB Output is correct
4 Correct 1128 ms 68244 KB Output is correct
5 Correct 108 ms 7252 KB Output is correct
6 Correct 105 ms 7248 KB Output is correct
7 Correct 106 ms 7256 KB Output is correct
8 Correct 107 ms 7252 KB Output is correct
9 Correct 103 ms 7248 KB Output is correct
10 Correct 105 ms 7248 KB Output is correct
11 Correct 133 ms 7180 KB Output is correct
12 Correct 100 ms 7252 KB Output is correct
13 Correct 107 ms 7252 KB Output is correct
14 Incorrect 1124 ms 68380 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 10 ms 584 KB Output isn't correct
3 Halted 0 ms 0 KB -