oj.uz

Submission #128118

# Submission time Handle Problem Language Result Execution time Memory
128118 2019-07-10T12:38:39 Z RockyB Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 1963 ms 85636 KB 
#include <bits/stdc++.h>

#define int ll

#define f first
#define s second

#define pb push_back
#define pp pop_back

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#define rep(a, b, c) for (int a = (b); (a) <= (c); ++a)
#define per(a, b, c) for (int a = (b); (a) >= (c); --a) 

#define nl '\n'
#define ioi exit(0);

using namespace std;

typedef long long ll;

const int MAX_N = (int)5e5 + 7;

int n, q;
int d[MAX_N], l[MAX_N], r[MAX_N], t[MAX_N], ans[MAX_N];

map <int, vector <int> > off;

int nxt[MAX_N], lst[MAX_N];
void prep() {
  int last = 1;
  rep(i, 1, n) {
    int df = (d[i] + last - 1) / last;
    lst[i] = df * last;
    last *= df;
  }
  per(i, n, 1) {
    if (lst[i] != lst[i + 1] || i == n) nxt[i] = i + 1;
    else nxt[i] = nxt[i + 1];
  }
}
vector < pair < pair <int, int>, ll > > a;
void solve(int T, vector <int> &qr) {
  int add = T, last = 1;
  a.clear();
  for (int i = 1, j = 0; i <= n; j = i + 1, i = nxt[i]) {
    int df = (d[i] + last - 1) / last;

    if (!sz(a)) a.pb({{0, i - 1}, i - 1});
    else a.pb({{j, i - 1}, {i - j}});
    a.pb({{i, i}, 1 + last * (add % df)});
    last *= df;
    add /= df;
    if (!add || nxt[i] > n) {
      if (i < n) a.pb({{i + 1, n}, {n - i}});
      break;
    }
  }
  for (auto it : qr) {
    int L = -1, R = -2;
    if (T >= l[it]) { // it's for right
      int ost = T - l[it];
      if (sz(a)) {
        R = min(ost, a[0].s);
      }
    }
    int sum = 0;
    rep(i, 0, sz(a) - 1) {
      sum += a[i].s;
      int val = T - sum;
      if (val >= l[it]) {
        R = a[i].f.s;
        
        int ost = val - l[it];
        if (i & 1 && i + 1 < sz(a)) {
          R += min(ost, a[i + 1].s);
        }
      }
      if (val <= r[it] && L == -1) {
        L = a[i].f.s;
        if (i % 2 == 0) {
          L -= max(0ll, min(r[it] - val, a[i].s - 1));
        }
      }
    }
    if (L != -1 && L <= R) ans[it] += R - L + 1;
  }
}
int32_t main() {
  // ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
    freopen ("C.out", "w", stdout);
  #endif
  scanf ("%lld %lld", &n, &q);
  d[0] = 1;
  rep(i, 1, n) {
    scanf ("%lld", &d[i]);
  }
  rep(i, 1, q) {
    scanf ("%lld %lld %lld", &t[i], &l[i], &r[i]);
    off[t[i]].pb(i);
  }
  prep();
  for (auto it : off) {
    solve(it.f, it.s);  
  }

  rep(i, 1, q) {
    printf ("%lld\n", ans[i]);
  }

  ioi
}

Compilation message

worst_reporter3.cpp: In function 'int32_t main()':
worst_reporter3.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld", &n, &q);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:100:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%lld", &d[i]);
     ~~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:103:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%lld %lld %lld", &t[i], &l[i], &r[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 85484 KB Output is correct
2 Correct 1535 ms 85552 KB Output is correct
3 Correct 1452 ms 85480 KB Output is correct
4 Correct 1393 ms 85608 KB Output is correct
5 Correct 1497 ms 85612 KB Output is correct
6 Correct 1377 ms 85604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 85484 KB Output is correct
2 Correct 1535 ms 85552 KB Output is correct
3 Correct 1452 ms 85480 KB Output is correct
4 Correct 1393 ms 85608 KB Output is correct
5 Correct 1497 ms 85612 KB Output is correct
6 Correct 1377 ms 85604 KB Output is correct
7 Correct 3 ms 508 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 508 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 1412 ms 83636 KB Output is correct
14 Correct 1402 ms 83704 KB Output is correct
15 Correct 1372 ms 83752 KB Output is correct
16 Correct 1391 ms 83548 KB Output is correct
17 Correct 1754 ms 85160 KB Output is correct
18 Correct 1793 ms 84992 KB Output is correct
19 Correct 1870 ms 85052 KB Output is correct
20 Correct 1780 ms 84968 KB Output is correct
21 Correct 1765 ms 85136 KB Output is correct
22 Correct 1796 ms 84980 KB Output is correct
23 Correct 1841 ms 84960 KB Output is correct
24 Correct 1801 ms 84972 KB Output is correct
25 Correct 1422 ms 85636 KB Output is correct
26 Correct 1421 ms 85484 KB Output is correct
27 Correct 1963 ms 85412 KB Output is correct
28 Correct 1904 ms 85380 KB Output is correct
29 Correct 1893 ms 85360 KB Output is correct
30 Correct 1935 ms 85448 KB Output is correct
31 Correct 1956 ms 85364 KB Output is correct
32 Correct 1382 ms 84980 KB Output is correct
33 Correct 2 ms 376 KB Output is correct