This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
struct seg {
ll val;
seg *l, *r;
seg() {val=0, l=r=NULL;}
void upd(ll s, ll e, ll fr, ll re) {
if (fr>re||val==(re-fr+1)) return ;
if (s<=fr&&re<=e) {val=(re-fr+1); return ;}
ll md=(fr+re)/2;
if (s<=md) {
if (!l) l=new seg();
l->upd(s, e, fr, md);
}
if (md+1<=e) {
if (!r) r=new seg();
r->upd(s, e, md+1, re);
}
val=(l?l->val:0)+(r?r->val:0);
}
};
seg *root=new seg();
int n; ll A, B;
ll l, r;
int main() {
scanf("%d %lld %lld", &n, &A, &B);
A/=__gcd(A, B+1);
if (1000000000000000000ll/B<=A) A=1000000000000000001ll;
else A*=B;
for (int i=0; i<n; i++) {
scanf("%lld %lld", &l, &r); l--; r--;
if (r-l+1>=A) {
printf("%lld\n", A);
return 0;
}
else {
r=(r-l)+l%A;
l%=A;
if (r>=A) {
root->upd(l, A-1, 0, A-1);
root->upd(0, r-A, 0, A-1);
}
else root->upd(l, r, 0, A-1);
}
}
printf("%lld\n", root->val);
return 0;
}
Compilation message (stderr)
strange_device.cpp: In function 'int main()':
strange_device.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld %lld", &n, &A, &B);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &l, &r); l--; r--;
~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |