oj.uz

Submission #752828

# Submission time Handle Problem Language Result Execution time Memory
752828 2023-06-04T03:05:56 Z winter0101 Strange Device (APIO19_strange_device) C++14
5 / 100
 449 ms 150008 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=1e6+9;
pll a[maxn];
vector<pll>b[maxn];
int bit[maxn];
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    int n;
    long long x,y;
    cin>>n>>x>>y;
    for1(i,1,n){
    cin>>a[i].fi>>a[i].se;
    }
    long long d=a[n].se/y;
    if (d<x){
        long long ans=0;
        for1(i,1,n){
        ans+=(a[i].se-a[i].fi+1);
        }
        cout<<ans;
        return 0;
    }
    long long z=x*y;
    if (n==1){
        long long d=(a[1].fi)/z;
        a[1].fi-=z*d;
        a[1].se-=z*d;
        long long t1=a[1].fi/z,t2=a[1].se/z;
        if (t1+1<t2){
            cout<<z;
            return 0;
        }
        if (t1==t2){
            cout<<(a[1].se-a[1].fi+1);
            return 0;
        }
        pll l1={a[1].fi,z-1};
        pll l2={0,a[1].se%z};
        if (l1.se>=l2.fi){
            cout<<z;
            return 0;
        }
        cout<<l1.se-l1.fi+1+l2.se-l2.fi+1;
        return 0;
    }
    for1(i,1,n){
    long long d=(a[i].fi)/z;
    a[i].fi-=z*d;
    a[i].se-=z*d;
    long long t1=a[1].fi/z,t2=a[1].se/z;
    if (t1+1<t2){
        b[i].pb({0,z-1});
        continue;
    }
    if (t1==t2){
        b[i].pb({a[i].fi%z,a[i].se%z});
        continue;
    }
    pll l1={a[1].fi,z-1};
    pll l2={0,a[1].se%z};
    b[i].pb(l1);
    b[i].pb(l2);
    }
    for1(i,1,n){
    for (auto v:b[i]){
        bit[v.fi]++;
        bit[v.se+1]--;
    }
    }
    int ans=0;
    for1(i,1,n){
    bit[i]+=bit[i-1];
    //if (bit[i])ans++;
    }
    for1(i,0,n){
    if (bit[i])ans++;
    }
    cout<<ans;
    
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Runtime error 35 ms 49476 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23784 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23828 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23824 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Runtime error 449 ms 150008 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Runtime error 449 ms 150008 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Runtime error 449 ms 150008 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Runtime error 66 ms 57592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23724 KB Output is correct
2 Runtime error 35 ms 49476 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -