oj.uz

답안 #256814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256814 2020-08-03T08:52:27 Z 2qbingxuan 이상한 기계 (APIO19_strange_device) C++17
65 / 100
 792 ms 66844 KB 
//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(...) qqbx(#__VA_ARGS__,  __VA_ARGS__)
template <typename H, typename ...T> constexpr void qqbx(const char *s, const H &h, T &&...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if constexpr(sizeof...(T)) qqbx(++s, args...); // C++ 17!
}
#else
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define get_pos(v,x) int(lower_bound(begin(v),end(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)

using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >;
template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-9;
constexpr ll N = 1000325, INF = 2e18, MOD = 1000000007, K = 105, inf = 1e9;
constexpr inline ll cdiv(ll x, ll m) { return x/m + ((x<0 ^ m>0) && (x%m)); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m=MOD) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    ll A, B;
    cin >> n >> A >> B;
    ll k = A / __gcd(A, B+1);
    if(k <= INF / B) k *= B;
    else k = INF;
    /* debug(k); */
    /* for(int i = 0; i < k; i++) { */
    /*     ll x = (i + i/B) % A; */
    /*     ll y = i%B; */
    /*     cout << x << ' ' << y << '\n'; */
    /* } */
    /* return 0; */
    vector<pair<ll,int>> evt;
    for(int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        ++r;
        l %= k;
        r %= k;
        if(l < r)
            evt.pb(l, 1), evt.pb(r, -1);
        else
            evt.pb(0, 1), evt.pb(r, -1), evt.pb(l, 1), evt.pb(k, -1);
    }
    evt.pb(k, 0);
    sort(all(evt));
    ll ans = 0;
    for(int i = 0, j, c = 0; i < evt.size(); i = j) {
        for(j = i; j < evt.size(); j++) {
            if(evt[j].first != evt[i].first) break;
            c += evt[j].second;
        }
        if(c && j != evt.size()) ans += evt[j].first - evt[i].first;
    }
    cout << ans << '\n';
}

Compilation message

strange_device.cpp:9:1: warning: multi-line comment [-Wcomment]
 //  \###################\
 ^
strange_device.cpp:16:0: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
 #pragma loop_opt(on)
 
strange_device.cpp: In function 'constexpr ll cdiv(ll, ll)':
strange_device.cpp:50:56: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
 constexpr inline ll cdiv(ll x, ll m) { return x/m + ((x<0 ^ m>0) && (x%m)); } // ceiling divide
                                                       ~^~
strange_device.cpp: In function 'int main()':
strange_device.cpp:83:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0, j, c = 0; i < evt.size(); i = j) {
                              ~~^~~~~~~~~~~~
strange_device.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = i; j < evt.size(); j++) {
                    ~~^~~~~~~~~~~~
strange_device.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(c && j != evt.size()) ans += evt[j].first - evt[i].first;
                 ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 6 ms 1408 KB Output is correct
17 Correct 74 ms 7276 KB Output is correct
18 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 647 ms 58464 KB Output is correct
3 Correct 696 ms 58524 KB Output is correct
4 Correct 641 ms 58540 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 647 ms 58464 KB Output is correct
3 Correct 696 ms 58524 KB Output is correct
4 Correct 641 ms 58540 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 631 ms 58516 KB Output is correct
7 Correct 618 ms 58528 KB Output is correct
8 Correct 662 ms 66844 KB Output is correct
9 Correct 775 ms 66456 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 647 ms 58464 KB Output is correct
3 Correct 696 ms 58524 KB Output is correct
4 Correct 641 ms 58540 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 61 ms 7276 KB Output is correct
7 Correct 67 ms 7280 KB Output is correct
8 Correct 66 ms 7272 KB Output is correct
9 Correct 68 ms 7280 KB Output is correct
10 Correct 63 ms 7284 KB Output is correct
11 Correct 64 ms 7276 KB Output is correct
12 Correct 58 ms 7276 KB Output is correct
13 Correct 69 ms 7272 KB Output is correct
14 Correct 64 ms 7280 KB Output is correct
15 Correct 72 ms 7272 KB Output is correct
16 Correct 71 ms 7276 KB Output is correct
17 Correct 60 ms 7372 KB Output is correct
18 Correct 685 ms 48256 KB Output is correct
19 Correct 671 ms 49672 KB Output is correct
20 Correct 781 ms 49728 KB Output is correct
21 Correct 74 ms 7280 KB Output is correct
22 Correct 61 ms 7372 KB Output is correct
23 Correct 193 ms 26708 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 80 ms 7276 KB Output is correct
3 Correct 81 ms 7272 KB Output is correct
4 Correct 792 ms 65440 KB Output is correct
5 Correct 72 ms 7272 KB Output is correct
6 Correct 70 ms 7276 KB Output is correct
7 Correct 68 ms 7276 KB Output is correct
8 Correct 82 ms 7272 KB Output is correct
9 Correct 67 ms 7376 KB Output is correct
10 Correct 71 ms 7276 KB Output is correct
11 Correct 71 ms 7276 KB Output is correct
12 Correct 60 ms 7276 KB Output is correct
13 Correct 75 ms 7276 KB Output is correct
14 Correct 753 ms 64796 KB Output is correct
15 Correct 72 ms 7280 KB Output is correct
16 Correct 616 ms 48956 KB Output is correct
17 Correct 616 ms 48960 KB Output is correct
18 Correct 0 ms 384 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1408 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 6 ms 1408 KB Output is correct
17 Correct 74 ms 7276 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Incorrect 0 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -