oj.uz

Submission #319291

# Submission time Handle Problem Language Result Execution time Memory
319291 2020-11-04T15:52:47 Z mohamedsobhi777 Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 657 ms 27492 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 5e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

int n, m;
int a[N];
ll per[N];

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;

        for (int i = 0; i < n; ++i)
                cin >> a[i];
        per[0] = a[0];
        for (int i = 1; i < n; ++i)
                per[i] = ceil(1.0 * a[i] / per[i - 1]) * per[i - 1];

        for (int i = 0; i < m; ++i)
        {

                int x, y, z;
                cin >> x >> y >> z;
                int l = 0, r = n - 1;
                int ans1 = -1, ans2 = -1;
                int k = 0;
                while (l <= r)
                {
                        int mid = (l + r) >> 1;
                        int pos = -(mid + 1);
                        int d = x / per[mid];
                        pos += d * per[mid];
                        if (pos >= y)
                        {
                                ans1 = mid;
                                l = mid + 1;
                        }
                        else
                                r = mid - 1;
                }
                l = 0, r = ans1;
                while (l <= r)
                {
                        int mid = (l + r) >> 1;
                        int pos = -(mid + 1);
                        int d = x / per[mid];
                        pos += d * per[mid];
                        if (pos <= z)
                        {
                                ans2 = mid;
                                r = mid - 1;
                        }
                        else
                                l = mid + 1;
                }
                int ans = 0 ; 
                if(ans1== -1 || ans2 == -1);else ans = ans1 - ans2 + 1; 
                cout << ans + (x >= y && x <= z) << "\n";
        }
        return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:49:21: warning: unused variable 'k' [-Wunused-variable]
   49 |                 int k = 0;
      |                     ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 9316 KB Output is correct
2 Correct 654 ms 24804 KB Output is correct
3 Correct 654 ms 24804 KB Output is correct
4 Correct 651 ms 24756 KB Output is correct
5 Correct 657 ms 24896 KB Output is correct
6 Correct 639 ms 24804 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 396 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 9316 KB Output is correct
2 Correct 654 ms 24804 KB Output is correct
3 Correct 654 ms 24804 KB Output is correct
4 Correct 651 ms 24756 KB Output is correct
5 Correct 657 ms 24896 KB Output is correct
6 Correct 639 ms 24804 KB Output is correct
7 Correct 1 ms 396 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 333 ms 23268 KB Output is correct
14 Correct 327 ms 24036 KB Output is correct
15 Correct 319 ms 22500 KB Output is correct
16 Correct 321 ms 23268 KB Output is correct
17 Correct 509 ms 27236 KB Output is correct
18 Correct 488 ms 27236 KB Output is correct
19 Correct 446 ms 27364 KB Output is correct
20 Correct 463 ms 27364 KB Output is correct
21 Correct 457 ms 27396 KB Output is correct
22 Correct 464 ms 27364 KB Output is correct
23 Correct 459 ms 27236 KB Output is correct
24 Correct 460 ms 27492 KB Output is correct
25 Correct 650 ms 24804 KB Output is correct
26 Correct 646 ms 24804 KB Output is correct
27 Correct 549 ms 26980 KB Output is correct
28 Correct 550 ms 27416 KB Output is correct
29 Correct 531 ms 26724 KB Output is correct
30 Correct 550 ms 26844 KB Output is correct
31 Correct 529 ms 27108 KB Output is correct
32 Correct 503 ms 23396 KB Output is correct
33 Correct 1 ms 364 KB Output is correct