oj.uz

Submission #982431

# Submission time Handle Problem Language Result Execution time Memory
982431 2024-05-14T08:50:42 Z vjudge1 Strange Device (APIO19_strange_device) C++17
25 / 100
 5000 ms 511404 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
using namespace std;
vll val,vval;int sz;
struct node{
    ll sum,mn,cnt;
    node operator+(node b){
        node c;c.sum=sum+b.sum;
        if(mn==b.mn)c.mn=mn,c.cnt=cnt+b.cnt;
        else if(mn<b.mn)c.mn=mn,c.cnt=cnt;
        else c.mn=b.mn,c.cnt=b.cnt;
        return c;
    }
};
vector<node>t;
vector<ll>lz;
void build(int i,int l,int r){
    if(l==r)return void(t[i]={0,0,vval[l]-vval[l-1]});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void push(int i,int l,int r){
    t[i].sum+=lz[i]*(vval[r]-vval[l-1]);
    t[i].mn+=lz[i];
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void upd(int i,int l,int r,int tl,int tr,ll v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=v;push(i,l,r);return;
    }int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
    t[i]=t[2*i]+t[2*i+1];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,a,b,d;cin>>n>>a>>b;d=a/__gcd(a,b+1);val.pb(0);val.pb(d);
    ll ans=0;vector<pair<ll,pll>>v;
    for(int i=0;i<n;i++){
        ll l,r;cin>>l>>r;ans+=r-l+1;
        ll x=l/b,y=r/b,z=l%b,tt=r%b;
        if(z<=tt){
            if(0<=z-1&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({z,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
            if(z<=tt&&x<=y)v.pb({z,{x,y}}),v.pb({tt+1,{-x,-y}}),val.pb(x%d),val.pb((y)%d+1);
            if(tt+1<=b-1&&x<=y-1)v.pb({tt+1,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
        }
        else {
            if(0<=tt&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({tt+1,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
            if(tt+1<=z-1&&x+1<=y-1)v.pb({tt+1,{x+1,y-1}}),v.pb({z,{-x-1,-y+1}}),val.pb((x+1)%d),val.pb((y-1+d)%d+1);
            if(z<=b-1&&x<=y-1)v.pb({z,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
        }
    }sort(v.begin(),v.end());sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());vval=val;vval.pb(d);
    sz=(int)val.size();t.resize(4*((int)val.size()+1)),lz.resize(4*((int)val.size()+1),0);build(1,1,sz);
    for(int i=0;i<v.size()-1;i++){
        ll x=abs(v[i].s.f)/d,y=abs(v[i].s.s)/d,z=abs(v[i].s.f)%d,tt=abs(v[i].s.s)%d;
        ll add=y-x+1;
        //cout<<v[i].f<<' '<<v[i].s.f<<' '<<v[i].s.s<<'\n';
        if(v[i].s.f>=0&&v[i].s.s>=0){
            if(z<=tt){
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,add);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
            }
            else {
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,add-2);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
            }
        }
        else {
            if(z<=tt){
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,-add);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
            }
            else {
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+2);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
            }
        }
        ans-=(v[i+1].f-v[i].f)*(t[1].sum-d);
        if(t[1].mn==0)ans-=(v[i+1].f-v[i].f)*t[1].cnt;
        //cout<<ans<<' '<<t[1].mn<<' '<<t[1].sum<<'\n';
        //if(v[i+1].f!=0)break;
    }cout<<ans;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<v.size()-1;i++){
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 16 ms 1908 KB Output is correct
3 Correct 15 ms 1904 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 0 ms 348 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 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 1 ms 348 KB Output is correct
16 Correct 21 ms 1772 KB Output is correct
17 Correct 140 ms 11924 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 8 ms 1116 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 6 ms 1012 KB Output is correct
5 Correct 548 ms 88944 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3369 ms 243328 KB Output is correct
3 Correct 3305 ms 245176 KB Output is correct
4 Correct 3223 ms 245520 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3369 ms 243328 KB Output is correct
3 Correct 3305 ms 245176 KB Output is correct
4 Correct 3223 ms 245520 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Execution timed out 5081 ms 446628 KB Time limit exceeded
7 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 3369 ms 243328 KB Output is correct
3 Correct 3305 ms 245176 KB Output is correct
4 Correct 3223 ms 245520 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 548 ms 31440 KB Output is correct
7 Correct 953 ms 54632 KB Output is correct
8 Correct 874 ms 53400 KB Output is correct
9 Correct 903 ms 52532 KB Output is correct
10 Correct 506 ms 25772 KB Output is correct
11 Correct 975 ms 52820 KB Output is correct
12 Correct 911 ms 55120 KB Output is correct
13 Correct 611 ms 47264 KB Output is correct
14 Correct 89 ms 11568 KB Output is correct
15 Correct 1004 ms 40096 KB Output is correct
16 Correct 232 ms 11740 KB Output is correct
17 Correct 1036 ms 54248 KB Output is correct
18 Execution timed out 5098 ms 511404 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 182 ms 11700 KB Output is correct
3 Correct 245 ms 12048 KB Output is correct
4 Execution timed out 5082 ms 185988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 16 ms 1908 KB Output is correct
3 Correct 15 ms 1904 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 0 ms 348 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 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 1 ms 348 KB Output is correct
16 Correct 21 ms 1772 KB Output is correct
17 Correct 140 ms 11924 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 8 ms 1116 KB Output is correct
26 Correct 2 ms 676 KB Output is correct
27 Correct 6 ms 1012 KB Output is correct
28 Correct 548 ms 88944 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 3369 ms 243328 KB Output is correct
31 Correct 3305 ms 245176 KB Output is correct
32 Correct 3223 ms 245520 KB Output is correct
33 Correct 0 ms 600 KB Output is correct
34 Execution timed out 5081 ms 446628 KB Time limit exceeded
35 Halted 0 ms 0 KB -