oj.uz

Submission #752836

# Submission time Handle Problem Language Result Execution time Memory
752836 2023-06-04T03:36:35 Z winter0101 Strange Device (APIO19_strange_device) C++14
10 / 100
 1155 ms 190244 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];
struct cus{
long long l,r;
bool operator < (const cus &p)const {
if (r==p.r)return l<p.l;
return r<p.r;
}
};
int bit[maxn*2];
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 d1=a[n].se/y;
    if (d1<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<long long>cord;
    for1(i,1,n){
    for (auto v:b[i]){
        cord.pb(v.fi);
        cord.pb(v.se+1);
    }
    }
    sort(all(cord));
    vector<long long>::iterator it=unique(all(cord));
    cord.resize(distance(cord.begin(),it));
    map<long long,int>newcord;
    for1(i,0,sz(cord)-1){
    newcord[cord[i]]=i;
    }
    for1(i,1,n){
    for (auto &v:b[i]){
        v.fi=newcord[v.fi];
        bit[v.fi]++;
        bit[newcord[v.se+1]]--;
    }
    }
    for1(i,1,sz(cord)-1){
    bit[i]+=bit[i-1];
    }
    long long ans=0;
    for1(i,0,sz(cord)-2){
    if (bit[i]){
        ans+=cord[i+1]-cord[i];
    }
    }
    for1(i,sz(cord)-1,sz(cord)-1){
    if (bit[i]){
        ans++;
    }
    }
    cout<<ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 19 ms 25092 KB Output is correct
3 Correct 18 ms 25388 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23692 KB Output is correct
3 Correct 12 ms 23776 KB Output is correct
4 Correct 12 ms 23784 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 11 ms 23752 KB Output is correct
2 Correct 12 ms 23880 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 12 ms 23892 KB Output is correct
5 Correct 336 ms 87296 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 1148 ms 153024 KB Output is correct
3 Incorrect 1047 ms 153168 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 1148 ms 153024 KB Output is correct
3 Incorrect 1047 ms 153168 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 1148 ms 153024 KB Output is correct
3 Incorrect 1047 ms 153168 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 Correct 108 ms 36676 KB Output is correct
3 Correct 113 ms 40552 KB Output is correct
4 Correct 1155 ms 190244 KB Output is correct
5 Correct 109 ms 40376 KB Output is correct
6 Correct 111 ms 40444 KB Output is correct
7 Correct 108 ms 40484 KB Output is correct
8 Correct 111 ms 40372 KB Output is correct
9 Correct 108 ms 40456 KB Output is correct
10 Correct 110 ms 40440 KB Output is correct
11 Correct 113 ms 40464 KB Output is correct
12 Correct 102 ms 40364 KB Output is correct
13 Correct 117 ms 40432 KB Output is correct
14 Correct 1081 ms 189976 KB Output is correct
15 Incorrect 117 ms 40384 KB Output isn't correct
16 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 Correct 19 ms 25092 KB Output is correct
3 Correct 18 ms 25388 KB Output is correct
4 Incorrect 11 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -