Submission #935568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935568	2024-02-29T09:20:28 Z	sysia	Strange Device (APIO19_strange_device)	C++17	5 / 100	982 ms	162808 KB

strange_device

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, A, B; cin >> n >> A >> B; 
    //po obrzydliwych obliczeniach dostajemy ze co AB to sie powtarza + dziala na samplach
    //jesli s \neq t mod AB, to daja rozne pary, nie wprost daja
    //wiec musi s \equiv t mod B, ale wtedy s \neq t mod A (bo gdyby zachodzilo przystawanie, to mozna wymnozyc(?))
    //czy to ze AB niekoniecznie wzglednie pierwsze przeszkadza w czyms?
    //wiec wtedy pierwsza wartosc daje inna reszte
    set<T>s;//przedzialy mod AB
    int C = A*B;
    for (int i = 0; i<n; i++){
        int l, r; cin >> l >> r;
        int L = l%C;
        int R = r%C;
        if (r-l+1 >= C) {
            s.insert({0, C-1});
        } else {
            if (L <= R) s.insert({L, R});
            else {
                s.insert({L, C-1});
                s.insert({0, R});
            }
        }
    }
    debug(s);
    map<int, int>sweep;
    for (auto [a, b]: s){
        sweep[a]++;
        sweep[b+1]--;
    }
    int prev = -1;
    int open = 0, ans = 0;
    for (auto [a, val]: sweep){
        debug(a, val, open);
        if (open) {
            ans += a-prev;
        }
        open += val;
        prev = a;
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Incorrect	348 KB	Output isn't correct
6	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	600 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	191 ms	25504 KB	Output is correct

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	775 ms	162692 KB	Output is correct
3	Incorrect	778 ms	162560 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	775 ms	162692 KB	Output is correct
3	Incorrect	778 ms	162560 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	775 ms	162692 KB	Output is correct
3	Incorrect	778 ms	162560 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	69 ms	16544 KB	Output is correct
3	Correct	77 ms	16536 KB	Output is correct
4	Correct	761 ms	162684 KB	Output is correct
5	Correct	81 ms	16604 KB	Output is correct
6	Correct	66 ms	16456 KB	Output is correct
7	Correct	66 ms	16508 KB	Output is correct
8	Correct	68 ms	16464 KB	Output is correct
9	Correct	65 ms	16468 KB	Output is correct
10	Correct	72 ms	16572 KB	Output is correct
11	Correct	69 ms	16464 KB	Output is correct
12	Correct	65 ms	16444 KB	Output is correct
13	Correct	66 ms	16464 KB	Output is correct
14	Correct	982 ms	162808 KB	Output is correct
15	Incorrect	69 ms	16520 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

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

Submission #935568

Compilation message