oj.uz

Submission #1115919

# Submission time Handle Problem Language Result Execution time Memory
1115919 2024-11-21T04:16:31 Z gdragon Strange Device (APIO19_strange_device) C++17
15 / 100
 259 ms 66528 KB 
#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e6 + 5;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
long long A, B;
int n;
pair<long long, long long> a[N];
void read() {
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
}
pair<long long, long long> cal(long long t) {
    // return mp(1, 1);
    return mp((t + (t / B)) % A, t % B);
}
void sub1() {
    map<pair<long long, long long>, bool> m;
    for(int i = 1; i <= n; i++) {
        for(long long j = a[i].fi; j <= a[i].se; j++) {
            m[cal(j)] = 1;
        }
    }
    cout << SZ(m);
}
bool check1() {
    long long sum = 0;
    for(int i = 1; i <= n; i++) sum += (a[i].se - a[i].fi + 1);
    // cerr << sum << endl;
    return (sum <= (int)1e6);
}
vector<pair<long long, long long>> seg;
void add(pair<long long, long long> tmp) {
    long long r = (2LL * tmp.fi) % A;
    cerr << tmp.fi << ' ' << tmp.se << ' ' << r << endl;
    if ((r & 1) == ((A - 1) & 1)) {
        long long rig = (A - 1);
        long long len = tmp.se - tmp.fi + 1;
        if (len > A / 2 + (A & 1)) {
            // cerr << "TRUE\n";
            if (r & 1) cerr << 1 << ' ' << rig << endl;
            else cerr << 0 << ' ' << rig << endl;
            if (r & 1) seg.push_back({1, rig});
            else seg.push_back({0, rig});
        }
        else {
            long long cnt = (rig - r) / 2 + 1;
            if (cnt >= len) {
                seg.push_back({r, r + 2 * (len - 1)});
                cerr << r << ' ' << r + 2 * (len - 1) << endl;
            }
            else {
                seg.push_back({r, rig});
                len -= cnt;
                cerr << r << ' ' << rig << endl;
                if (A & 1) cerr << 0 << ' ' << 2 * (len - 1) << endl;
                else cout << 1 << ' ' << 1 + 2 * (len - 1) << endl;
                if (A & 1) seg.push_back(mp(0, 2 * (len - 1)));
                else seg.push_back({1LL, 1 + 2LL * (len - 1)});
            }
        }
    }
    else {
        // cerr << "FALSE: " << tmp.fi << ' ' << tmp.se << ' ' << r << endl;
        // assert(false);
    }
}
void sub4() {
    for(int i = 1; i <= n; i++) {
        for(int iter = 0; iter < 3; iter++) {
            long long len = a[i].se - a[i].fi + 1;
            if (len <= 0) break;
            long long r = 2LL * a[i].fi % A;
            long long rig = (A - 1) - (((A - 1) & 1) != (r & 1));
            long long cnt = (rig - r) / 2 + 1;
            if (cnt >= len) {
                seg.push_back({r, r + 2 * (len - 1)});
                break;
            }
            else {
                seg.push_back({r, rig});
                a[i].fi += cnt;
            }
        }
    }
    sort(ALL(seg));
    vector<pair<long long, long long>> odd, even;
    for(auto &i: seg) {
        if (i.fi & 1) odd.push_back(i);
        else even.push_back(i);
        // cout << i.fi << ' ' << i.se << endl;
    }
    long long ans = 0;
    for(int i = 0; i < SZ(odd); i++) {
        int j = i;
        while(j + 1 < SZ(odd) && odd[j + 1].fi <= odd[j].se) ++j;
        ans += (odd[j].se - odd[i].fi) / 2 + 1;
        i = j;
    }
    for(int i = 0; i < SZ(even); i++) {
        int j = i;
        while(j + 1 < SZ(even) && even[j + 1].fi <= even[j].se) ++j;
        ans += (even[j].se - even[i].fi) / 2 + 1;
        i = j;
    }
    cout << ans;
}
void solve() {
    if (check1()) {
        sub1();
        return;
    }
    if (B == 1) sub4();
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 36 ms 12504 KB Output is correct
3 Correct 54 ms 18500 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 7 ms 1360 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 30 ms 7152 KB Output is correct
16 Correct 23 ms 7248 KB Output is correct
17 Correct 54 ms 12492 KB Output is correct
18 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 95 ms 32328 KB Output is correct
3 Correct 109 ms 32072 KB Output is correct
4 Correct 91 ms 30792 KB Output is correct
5 Incorrect 164 ms 41192 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 66528 KB Output is correct
3 Correct 257 ms 59104 KB Output is correct
4 Correct 252 ms 59048 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 66528 KB Output is correct
3 Correct 257 ms 59104 KB Output is correct
4 Correct 252 ms 59048 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 238 ms 15996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 259 ms 66528 KB Output is correct
3 Correct 257 ms 59104 KB Output is correct
4 Correct 252 ms 59048 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Incorrect 23 ms 2640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 23 ms 2640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 36 ms 12504 KB Output is correct
3 Correct 54 ms 18500 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 7 ms 1360 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 30 ms 7152 KB Output is correct
16 Correct 23 ms 7248 KB Output is correct
17 Correct 54 ms 12492 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Incorrect 1 ms 336 KB Output isn't correct
21 Halted 0 ms 0 KB -