oj.uz

Submission #984873

# Submission time Handle Problem Language Result Execution time Memory
984873 2024-05-17T07:39:19 Z SyedSohaib_123 Strange Device (APIO19_strange_device) C++17
0 / 100
 1134 ms 33320 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 604 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 348 KB Output is correct
2 Correct 0 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 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 106 ms 3668 KB Output is correct
3 Correct 110 ms 3700 KB Output is correct
4 Correct 1134 ms 33288 KB Output is correct
5 Correct 106 ms 3668 KB Output is correct
6 Correct 106 ms 3704 KB Output is correct
7 Correct 105 ms 3500 KB Output is correct
8 Correct 108 ms 3656 KB Output is correct
9 Correct 112 ms 3636 KB Output is correct
10 Correct 105 ms 3664 KB Output is correct
11 Correct 105 ms 3664 KB Output is correct
12 Correct 128 ms 3592 KB Output is correct
13 Correct 106 ms 3668 KB Output is correct
14 Incorrect 1096 ms 33044 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 604 KB Output isn't correct
3 Halted 0 ms 0 KB -