oj.uz

Submission #641539

# Submission time Handle Problem Language Result Execution time Memory
641539 2022-09-17T02:48:27 Z baojiaopisu Strange Device (APIO19_strange_device) C++14
10 / 100
 5000 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 5e18;
const int N = 1e5 + 10;

ll gcd(ll x, ll y) {
    if(y == 0) return x;
    return gcd(y, x % y);
}

ll lcm(ll x, ll y) {
    ll ans = x / gcd(x, y);
    if(INF / ans < y) return -1;
    return ans * y;
}

map<ll, int> cnt;

void solve() {
	int n; ll A, B; cin >> n >> A >> B;
    ll m = A / gcd(B + 1, A);
    if(INF / m < B) m = -1;
    else m = m * B;

    if(m == -1) m = INF;

    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ll L, R; cin >> L >> R;
        for(ll j = L; j <= R; j++) {
            ll r = j % m;
            if(!cnt[r]) ++ans;
            cnt[r] = true;
        }
    }

    cout << ans;
}

int main()
{

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        solve();
    }
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:107:17: warning: unused variable 'ddd' [-Wunused-variable]
  107 |     int tc = 1, ddd = 0;
      |                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 63 ms 12672 KB Output is correct
3 Correct 103 ms 18248 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 40 ms 7020 KB Output is correct
16 Correct 36 ms 6988 KB Output is correct
17 Correct 165 ms 10224 KB Output is correct
18 Correct 1 ms 300 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5068 ms 513032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 137 ms 32180 KB Output is correct
3 Correct 138 ms 32052 KB Output is correct
4 Correct 145 ms 30536 KB Output is correct
5 Execution timed out 5074 ms 62408 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1534 ms 65444 KB Output is correct
3 Runtime error 2603 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1534 ms 65444 KB Output is correct
3 Runtime error 2603 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1534 ms 65444 KB Output is correct
3 Runtime error 2603 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2627 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 63 ms 12672 KB Output is correct
3 Correct 103 ms 18248 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 40 ms 7020 KB Output is correct
16 Correct 36 ms 6988 KB Output is correct
17 Correct 165 ms 10224 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Execution timed out 5068 ms 513032 KB Time limit exceeded
21 Halted 0 ms 0 KB -