oj.uz

Submission #260694

# Submission time Handle Problem Language Result Execution time Memory
260694 2020-08-10T18:17:05 Z tko919 Strange Device (APIO19_strange_device) C++17
0 / 100
 1 ms 256 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

typedef pair<ll,ll> P;

int main(){
   ll n,a,b; cin>>n>>a>>b;
   ll g=a/gcd(a,b+1);
   if(b>INF/g)g=INF; else g*=b;
   vector<P> rng; vector<ll> vs={0,g};
   rep(i,0,n){
      ll lb,rb; cin>>lb>>rb; rb++;
      lb%=g; rb%=g;
      vs.push_back(lb);
      vs.push_back(rb);
      if(lb<=rb){
         rng.push_back({lb,1});
         rng.push_back({rb,-1});
      }
      else{
         rng.push_back({0,1});
         rng.push_back({rb,-1});
         rng.push_back({lb,1});
         rng.push_back({g,-1});
      }
   }
   sort(ALL(vs)); vs.erase(unique(ALL(vs)),vs.end());
   map<ll,int> rev;
   rep(i,0,vs.size())rev[vs[i]]=i;
   int m=vs.size();
   vector<ll> rui(m+10,0);
   rep(i,0,rng.size())rui[rev[rng[i].first]]+=rng[i].second;
   rep(i,0,m-1)rui[i+1]+=rui[i];
   ll res=0;
   rep(i,0,m-1){
      if(rui[i])res+=vs[i+1]-vs[i];
   }
   cout<<res<<endl;
   return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -