oj.uz

답안 #982458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982458 2024-05-14T09:24:54 Z vjudge1 이상한 기계 (APIO19_strange_device) C++17
45 / 100
 5000 ms 411012 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;
vector<pll>t;
vector<ll>lz;
void build(int i,int l,int r){
    if(l==r)return void(t[i]={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]={0,t[2*i].s+t[2*i+1].s};
}
void push(int i,int l,int r){
    t[i].f+=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);
    if(t[2*i].f==t[2*i+1].f)t[i]={t[2*i].f,t[2*i].s+t[2*i+1].s};
    else t[i]=min(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;
        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;
        if(v[i].s.f>=0&&v[i].s.s>=0){
            if(z<=tt){
                int tl=upper_bound(val.begin(),val.end(),z)-val.begin();
                int tr=upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,1,tl-1,add-1);
                upd(1,1,sz,tl,tr-1,add);
                upd(1,1,sz,tr,sz-1,add-1);
            }
            else {
                int tl=upper_bound(val.begin(),val.end(),z)-val.begin();
                int tr=upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,1,tr-1,add-1);
                upd(1,1,sz,tr,tl-1,add-2);
                upd(1,1,sz,tl,sz-1,add-1);
            }
        }
        else {
            if(z<=tt){
                int tl=upper_bound(val.begin(),val.end(),z)-val.begin();
                int tr=upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,1,tl-1,-add+1);
                upd(1,1,sz,tl,tr-1,-add);
                upd(1,1,sz,tr,sz-1,-add+1);
            }
            else {
                int tl=upper_bound(val.begin(),val.end(),z)-val.begin();
                int tr=upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,1,tr-1,-add+1);
                upd(1,1,sz,tr,tl-1,-add+2);
                upd(1,1,sz,tl,sz-1,-add+1);
            }
        }
        if(t[1].f==0)ans+=(v[i+1].f-v[i].f)*(d-t[1].s);
    }cout<<ans;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 13 ms 1396 KB Output is correct
3 Correct 11 ms 1396 KB Output is correct
4 Correct 0 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 348 KB Output is correct
9 Correct 1 ms 344 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 1 ms 348 KB Output is correct
16 Correct 19 ms 1396 KB Output is correct
17 Correct 111 ms 9552 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 7 ms 980 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 494 ms 64356 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2769 ms 174676 KB Output is correct
3 Correct 2656 ms 174176 KB Output is correct
4 Correct 2666 ms 175520 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2769 ms 174676 KB Output is correct
3 Correct 2656 ms 174176 KB Output is correct
4 Correct 2666 ms 175520 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Execution timed out 5063 ms 346964 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2769 ms 174676 KB Output is correct
3 Correct 2656 ms 174176 KB Output is correct
4 Correct 2666 ms 175520 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 414 ms 24016 KB Output is correct
7 Correct 686 ms 42908 KB Output is correct
8 Correct 674 ms 45728 KB Output is correct
9 Correct 670 ms 43700 KB Output is correct
10 Correct 382 ms 20980 KB Output is correct
11 Correct 713 ms 43452 KB Output is correct
12 Correct 678 ms 45728 KB Output is correct
13 Correct 485 ms 36268 KB Output is correct
14 Correct 77 ms 9324 KB Output is correct
15 Correct 731 ms 31716 KB Output is correct
16 Correct 179 ms 8572 KB Output is correct
17 Correct 800 ms 44444 KB Output is correct
18 Execution timed out 5023 ms 411012 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 166 ms 10260 KB Output is correct
3 Correct 213 ms 10452 KB Output is correct
4 Correct 4557 ms 153316 KB Output is correct
5 Correct 262 ms 10700 KB Output is correct
6 Correct 250 ms 11728 KB Output is correct
7 Correct 218 ms 10176 KB Output is correct
8 Correct 315 ms 12480 KB Output is correct
9 Correct 288 ms 12548 KB Output is correct
10 Correct 174 ms 9708 KB Output is correct
11 Correct 94 ms 10956 KB Output is correct
12 Correct 108 ms 10296 KB Output is correct
13 Correct 256 ms 11220 KB Output is correct
14 Correct 1804 ms 83144 KB Output is correct
15 Correct 150 ms 10332 KB Output is correct
16 Correct 1451 ms 83004 KB Output is correct
17 Correct 4009 ms 151376 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 13 ms 1396 KB Output is correct
3 Correct 11 ms 1396 KB Output is correct
4 Correct 0 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 348 KB Output is correct
9 Correct 1 ms 344 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 1 ms 348 KB Output is correct
16 Correct 19 ms 1396 KB Output is correct
17 Correct 111 ms 9552 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 7 ms 980 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 4 ms 604 KB Output is correct
28 Correct 494 ms 64356 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 2769 ms 174676 KB Output is correct
31 Correct 2656 ms 174176 KB Output is correct
32 Correct 2666 ms 175520 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Execution timed out 5063 ms 346964 KB Time limit exceeded
35 Halted 0 ms 0 KB -