oj.uz

Submission #210184

# Submission time Handle Problem Language Result Execution time Memory
210184 2020-03-16T19:22:06 Z tatyam Strange Device (APIO19_strange_device) C++17
65 / 100
 759 ms 69600 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using pcc = pair<char, char>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using tuplis = array<ll, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF=0x1fffffffffffffff;
const ll MINF=0x7fffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
const int MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ld PI=3.1415926535897932;
const ll dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const ll dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=(n)-1;i>=0;i--)
#define rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define each(i,...) for(auto&& i:__VA_ARGS__)
#define all1(i) begin(i),end(i)
#define all2(i,a) begin(i),begin(i)+a
#define all3(i,a,b) begin(i)+a,begin(i)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(i) (i).rbegin(),(i).rend()
#define rall2(i,k) (i).rbegin(),(i).rbegin()+k
#define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define elif else if
#define unless(a) if(!(a))
#define mp make_pair
#define mt make_tuple
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define Sort(a) sort(all(a))
#define Rev(a) reverse(all(a))
#define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
vector<pll> factor(ull x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
template<class T> unordered_map<T, ll> press(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); unordered_map<T,ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
template<class T> map<T, ll> press_map(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); map<T,ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long& a){ scanf("%ld", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long a){ printf("%ld", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(const char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#ifdef DEBUG
void err(){ putchar('\n'); }
template<class T> void err(const T& t){ print(t); putchar('\n'); }
template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }
#else
template<class... T> void err(const T&...){}
#endif
int first(bool i = true){ return out(i?"first":"second"); }
int yes(bool i = true){ return out(i?"yes":"no"); }
int Yes(bool i = true){ return out(i?"Yes":"No"); }
int No(){ return out("No"); }
int YES(bool i = true){ return out(i?"YES":"NO"); }
int NO(){ return out("NO"); }
int Yay(bool i = true){ return out(i?"Yay!":":("); }
int possible(bool i = true){ return out(i?"possible":"impossible"); }
int Possible(bool i = true){ return out(i?"Possible":"Impossible"); }
int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); }
void Case(ll i){ printf("Case #%lld: ", i); }



using u128 = __uint128_t;
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ull n, a, b;
    cin >> n >> a >> b;
    u128 mod = a / gcd(a, b + 1) * u128(b);
    vector<pair<ull, int>> query;
    rep(n){
        ull l, r;
        cin >> l >> r;
        l--;
        if(r - l >= mod){
            cout << ull(mod) << endl;
            return 0;
        }
        r--;
        l %= mod; r %= mod;
        r++;
        query.emplace_back(l, 1);
        query.emplace_back(r, -1);
        if(l > r){
            query.emplace_back(mod, -1);
            query.emplace_back(0, 1);
        }
    }
    Sort(query);
    Rev(query);
    ull at = 0, cnt = 0, ans = 0;
    while(query.size()){
        ull next = query.back().first;
        if(cnt) ans += next - at;
        at = next;
        while(query.size() && query.back().first == at){
            cnt += query.back().second;
            query.pop_back();
        }
    }
    cout << ans << endl;
}

Compilation message

strange_device.cpp: In function 'std::vector<long long int> divisor(ull)':
strange_device.cpp:74:151: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 vector<ll> divisor(ull x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
                                                                                                                               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
strange_device.cpp:30:28: note: in definition of macro 'rrep1'
 #define rrep1(n) for(ll i=(n)-1;i>=0;i--)
                            ^
strange_device.cpp:74:108: note: in expansion of macro 'rrep'
 vector<ll> divisor(ull x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
                                                                                                            ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:25:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep1(n) for(ll i=0;i<n;++i)
                             ^
strange_device.cpp:23:41: note: in expansion of macro 'rep1'
 #define overload4(_1,_2,_3,_4,name,...) name
                                         ^~~~
strange_device.cpp:29:18: note: in expansion of macro 'overload4'
 #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
                  ^~~~~~~~~
strange_device.cpp:158:5: note: in expansion of macro 'rep'
     rep(n){
     ^~~
strange_device.cpp: In function 'void scan(int&)':
strange_device.cpp:78:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(int& a){ scanf("%d", &a); }
                    ~~~~~^~~~~~~~~~
strange_device.cpp: In function 'void scan(unsigned int&)':
strange_device.cpp:79:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(unsigned& a){ scanf("%u", &a); }
                         ~~~~~^~~~~~~~~~
strange_device.cpp: In function 'void scan(long int&)':
strange_device.cpp:80:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long& a){ scanf("%ld", &a); }
                     ~~~~~^~~~~~~~~~~
strange_device.cpp: In function 'void scan(long long int&)':
strange_device.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long long& a){ scanf("%lld", &a); }
                          ~~~~~^~~~~~~~~~~~
strange_device.cpp: In function 'void scan(long long unsigned int&)':
strange_device.cpp:82:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(unsigned long long& a){ scanf("%llu", &a); }
                                   ~~~~~^~~~~~~~~~~~
strange_device.cpp: In function 'void scan(float&)':
strange_device.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(float& a){ scanf("%f", &a); }
                      ~~~~~^~~~~~~~~~
strange_device.cpp: In function 'void scan(double&)':
strange_device.cpp:85:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(double& a){ scanf("%lf", &a); }
                       ~~~~~^~~~~~~~~~~
strange_device.cpp: In function 'void scan(long double&)':
strange_device.cpp:86:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(long double& a){ scanf("%Lf", &a); }
                            ~~~~~^~~~~~~~~~~
strange_device.cpp: In function 'void scan(char*)':
strange_device.cpp:88:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void scan(char a[]){ scanf("%s", a); }
                      ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 12 ms 1400 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 11 ms 1396 KB Output is correct
17 Correct 79 ms 7272 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 562 ms 69600 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 618 ms 38996 KB Output is correct
3 Correct 680 ms 38976 KB Output is correct
4 Correct 608 ms 38976 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 618 ms 38996 KB Output is correct
3 Correct 680 ms 38976 KB Output is correct
4 Correct 608 ms 38976 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 622 ms 38992 KB Output is correct
7 Correct 638 ms 38976 KB Output is correct
8 Correct 626 ms 38976 KB Output is correct
9 Correct 726 ms 38976 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 618 ms 38996 KB Output is correct
3 Correct 680 ms 38976 KB Output is correct
4 Correct 608 ms 38976 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 68 ms 7392 KB Output is correct
7 Correct 67 ms 7276 KB Output is correct
8 Correct 65 ms 7276 KB Output is correct
9 Correct 65 ms 7272 KB Output is correct
10 Correct 64 ms 7268 KB Output is correct
11 Correct 69 ms 7272 KB Output is correct
12 Correct 70 ms 7272 KB Output is correct
13 Correct 72 ms 7272 KB Output is correct
14 Correct 65 ms 7268 KB Output is correct
15 Correct 76 ms 7276 KB Output is correct
16 Correct 74 ms 7272 KB Output is correct
17 Correct 68 ms 7272 KB Output is correct
18 Correct 618 ms 38976 KB Output is correct
19 Correct 609 ms 38976 KB Output is correct
20 Correct 738 ms 38980 KB Output is correct
21 Correct 75 ms 7272 KB Output is correct
22 Correct 59 ms 7276 KB Output is correct
23 Correct 232 ms 43200 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 79 ms 7276 KB Output is correct
3 Correct 73 ms 7392 KB Output is correct
4 Correct 759 ms 38980 KB Output is correct
5 Correct 72 ms 7276 KB Output is correct
6 Correct 73 ms 7392 KB Output is correct
7 Correct 75 ms 7272 KB Output is correct
8 Correct 77 ms 7272 KB Output is correct
9 Correct 72 ms 7272 KB Output is correct
10 Correct 77 ms 7268 KB Output is correct
11 Correct 70 ms 7272 KB Output is correct
12 Correct 68 ms 7272 KB Output is correct
13 Correct 78 ms 7272 KB Output is correct
14 Correct 727 ms 38972 KB Output is correct
15 Correct 79 ms 7272 KB Output is correct
16 Correct 587 ms 38980 KB Output is correct
17 Correct 642 ms 38928 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 12 ms 1400 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 11 ms 1396 KB Output is correct
17 Correct 79 ms 7272 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Incorrect 5 ms 376 KB Output isn't correct
22 Halted 0 ms 0 KB -