oj.uz

Submission #985083

# Submission time Handle Problem Language Result Execution time Memory
985083 2024-05-17T10:30:02 Z SyedSohaib_123 Strange Device (APIO19_strange_device) C++17
35 / 100
 1599 ms 131340 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;
    int cnt=0;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        cnt+=y-x+1;
        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);
    map<int,int>hlpr;
    for(auto i:q) hlpr[i.ff]=i.ss;
    vector<pii>q2;
    for(auto i:hlpr) q2.append(i);
    hlpr.clear();
    swap(q2,q);
    for(int i=1;i<q.size();i++){
        if(q[i-1].ss>=q[i].ff){
            q[i].ss=max(q[i].ss,q[i-1].ss);
            q[i].ff=q[i-1].ff;
            hlpr[i-1]=1;
        }
    }
    q2.clear();
    int ans=0;
    for(int i=0;i<q.size();i++){
        if(hlpr[i]){continue;}
        ans+=q[i].ss-q[i].ff+1;
    }
    cout<<ans<<endl;

}
 
 
 
 
 
signed main(){
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:86: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]
   86 |     for(int i=1;i<q.size();i++){
      |                 ~^~~~~~~~~
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=0;i<q.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 12 ms 1368 KB Output is correct
3 Correct 13 ms 1368 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 12 ms 1372 KB Output is correct
17 Correct 147 ms 11368 KB Output is correct
18 Incorrect 0 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 747 ms 33224 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1480 ms 112228 KB Output is correct
3 Correct 1415 ms 111996 KB Output is correct
4 Correct 1446 ms 112088 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1480 ms 112228 KB Output is correct
3 Correct 1415 ms 111996 KB Output is correct
4 Correct 1446 ms 112088 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1469 ms 112108 KB Output is correct
7 Correct 1501 ms 112168 KB Output is correct
8 Correct 1522 ms 112248 KB Output is correct
9 Correct 1549 ms 112368 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1480 ms 112228 KB Output is correct
3 Correct 1415 ms 111996 KB Output is correct
4 Correct 1446 ms 112088 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 149 ms 11436 KB Output is correct
7 Correct 130 ms 11372 KB Output is correct
8 Correct 127 ms 11600 KB Output is correct
9 Correct 131 ms 11432 KB Output is correct
10 Correct 153 ms 11604 KB Output is correct
11 Correct 133 ms 11572 KB Output is correct
12 Correct 139 ms 11452 KB Output is correct
13 Correct 136 ms 11604 KB Output is correct
14 Correct 132 ms 11604 KB Output is correct
15 Correct 137 ms 11604 KB Output is correct
16 Correct 137 ms 11652 KB Output is correct
17 Correct 133 ms 11604 KB Output is correct
18 Correct 1440 ms 112252 KB Output is correct
19 Correct 1514 ms 130936 KB Output is correct
20 Correct 1599 ms 130820 KB Output is correct
21 Correct 144 ms 13904 KB Output is correct
22 Correct 140 ms 13652 KB Output is correct
23 Correct 383 ms 18144 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 149 ms 13908 KB Output is correct
3 Correct 138 ms 13904 KB Output is correct
4 Correct 1547 ms 131340 KB Output is correct
5 Correct 141 ms 13908 KB Output is correct
6 Correct 143 ms 14324 KB Output is correct
7 Correct 138 ms 13972 KB Output is correct
8 Correct 161 ms 13900 KB Output is correct
9 Correct 146 ms 13912 KB Output is correct
10 Correct 138 ms 13968 KB Output is correct
11 Correct 143 ms 13988 KB Output is correct
12 Correct 128 ms 13908 KB Output is correct
13 Correct 148 ms 13920 KB Output is correct
14 Correct 1517 ms 131332 KB Output is correct
15 Correct 132 ms 13656 KB Output is correct
16 Correct 1418 ms 130892 KB Output is correct
17 Correct 1470 ms 130900 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 12 ms 1368 KB Output is correct
3 Correct 13 ms 1368 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 12 ms 1372 KB Output is correct
17 Correct 147 ms 11368 KB Output is correct
18 Incorrect 0 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -