oj.uz

Submission #752833

# Submission time Handle Problem Language Result Execution time Memory
752833 2023-06-04T03:25:42 Z winter0101 Strange Device (APIO19_strange_device) C++14
10 / 100
 1223 ms 186156 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];
struct cus{
long long l,r;
bool operator < (const cus &p)const {
if (r==p.r)return l<p.l;
return r<p.r;
}
};
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;
    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[i].fi/z,t2=a[i].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[i].fi,z-1};
    pll l2={0,a[i].se%z};
    b[i].pb(l1);
    b[i].pb(l2);
    }
    vector<pll>ntr;
    for1(i,1,n){
    for (auto v:b[i]){
        ntr.pb(v);
        //cout<<v.fi<<" "<<v.se<<'\n';
    }
    }
    sort(all(ntr));
    set<cus>nt;
    set<cus>::iterator it;
    for (auto &v:ntr){
        if (nt.empty()){
            nt.insert({0,v.se});
            continue;
        }
        it=nt.lower_bound({0,v.fi});
        if (it==nt.end()){
            nt.insert({v.fi,v.se});
            continue;
        }
        cus tt=*it;
        nt.erase(it);
        tt.r=max(tt.r,v.se);
        nt.insert(tt);
    }
    long long ans=0;
    for (auto v:nt){
        ans+=v.r-v.l+1;
    }
    cout<<ans;

}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23736 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23868 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 373 ms 87332 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 1211 ms 149060 KB Output is correct
3 Incorrect 1223 ms 186156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 1211 ms 149060 KB Output is correct
3 Incorrect 1223 ms 186156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 1211 ms 149060 KB Output is correct
3 Incorrect 1223 ms 186156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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