oj.uz

Submission #136662

# Submission time Handle Problem Language Result Execution time Memory
136662 2019-07-26T05:36:07 Z KLPP Strange Device (APIO19_strange_device) C++14
35 / 100
 2755 ms 49176 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
lld GCD(lld x, lld y){
  if(y==0)return x;
  return GCD(y,x%y);
}

int main(){
  srand(time(NULL));
  lld n,A,B;
  cin>>n>>A>>B;
  /*n=1;
  A=rand()%100;
  B=rand()%100;*/
  lld l[n];
  lld r[n];
  rep(i,0,n){
    cin>>l[i]>>r[i];
    /*l[i]=rand()%200;
    r[i]=rand()%200;
    if(l[i]>r[i])swap(l[i],r[i]);*/
  }
  lld D=GCD(A,B+1);
  D=A/D;
  vector<pii> seg;
  rep(i,0,n){
    if(r[i]-l[i]+1>=D*B){
      cout<<D*B<<endl;
      return 0;
    }
    l[i]%=D*B;
    r[i]%=D*B;
    if(l[i]>r[i]){
      seg.push_back(pii(0,r[i]));
      seg.push_back(pii(l[i],D*B-1));
    }else{
      seg.push_back(pii(l[i],r[i]));
    }
  }
  sort(seg.begin(),seg.end());
  stack<pii> s;
  rep(i,0,seg.size()){
    //cout<<seg[i].first<<" "<<seg[i].second<<endl;
    if(s.empty() || seg[i].first>s.top().second){
      s.push(seg[i]);
    }else{
      s.top().second=max(s.top().second,seg[i].second);
    }
  }
  lld ans=0;
  while(!s.empty()){
    //cout<<s.top().first<<" "<<s.top().second<<endl;
    ans+=s.top().second-s.top().first+1;
    //cout<<ans<<endl;
    s.pop();
  }
  cout<<ans<<endl;
  //cout<<s.size()<<" "<<min(r[0]-l[0]+1,D*B)<<" "<<A<<" "<<B<<" "<<l[0]<<" "<<r[0]<<endl;
  //trav(a,s)cout<<a.first<<" "<<a.second<<endl;
  return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
strange_device.cpp:47:7:
   rep(i,0,seg.size()){
       ~~~~~~~~~~~~~~             
strange_device.cpp:47:3: note: in expansion of macro 'rep'
   rep(i,0,seg.size()){
   ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 1144 KB Output is correct
3 Correct 29 ms 1244 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 29 ms 1268 KB Output is correct
17 Correct 275 ms 5928 KB Output is correct
18 Incorrect 2 ms 296 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 372 KB Output is correct
4 Correct 5 ms 408 KB Output is correct
5 Correct 1918 ms 33136 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2671 ms 48376 KB Output is correct
3 Correct 2687 ms 48136 KB Output is correct
4 Correct 2682 ms 48228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2671 ms 48376 KB Output is correct
3 Correct 2687 ms 48136 KB Output is correct
4 Correct 2682 ms 48228 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2682 ms 48340 KB Output is correct
7 Correct 2693 ms 48284 KB Output is correct
8 Correct 2668 ms 48476 KB Output is correct
9 Correct 2754 ms 48660 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2671 ms 48376 KB Output is correct
3 Correct 2687 ms 48136 KB Output is correct
4 Correct 2682 ms 48228 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 271 ms 6284 KB Output is correct
7 Correct 275 ms 6116 KB Output is correct
8 Correct 275 ms 5828 KB Output is correct
9 Correct 297 ms 5896 KB Output is correct
10 Correct 268 ms 5820 KB Output is correct
11 Correct 270 ms 5788 KB Output is correct
12 Correct 268 ms 5684 KB Output is correct
13 Correct 273 ms 5816 KB Output is correct
14 Correct 267 ms 6120 KB Output is correct
15 Correct 274 ms 6272 KB Output is correct
16 Correct 273 ms 6292 KB Output is correct
17 Correct 270 ms 6296 KB Output is correct
18 Correct 2682 ms 48760 KB Output is correct
19 Correct 2672 ms 48976 KB Output is correct
20 Correct 2737 ms 48908 KB Output is correct
21 Correct 274 ms 6808 KB Output is correct
22 Correct 267 ms 6240 KB Output is correct
23 Correct 908 ms 18212 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 273 ms 6884 KB Output is correct
3 Correct 274 ms 6852 KB Output is correct
4 Correct 2755 ms 49176 KB Output is correct
5 Correct 274 ms 5188 KB Output is correct
6 Correct 272 ms 5176 KB Output is correct
7 Correct 273 ms 5172 KB Output is correct
8 Correct 272 ms 5132 KB Output is correct
9 Correct 270 ms 5236 KB Output is correct
10 Correct 273 ms 5228 KB Output is correct
11 Correct 271 ms 5188 KB Output is correct
12 Correct 264 ms 5396 KB Output is correct
13 Correct 275 ms 5224 KB Output is correct
14 Correct 2725 ms 48048 KB Output is correct
15 Correct 275 ms 4948 KB Output is correct
16 Correct 2656 ms 47976 KB Output is correct
17 Correct 2656 ms 48488 KB Output is correct
18 Incorrect 2 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 29 ms 1144 KB Output is correct
3 Correct 29 ms 1244 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 29 ms 1268 KB Output is correct
17 Correct 275 ms 5928 KB Output is correct
18 Incorrect 2 ms 296 KB Output isn't correct