oj.uz

Submission #47456

# Submission time Handle Problem Language Result Execution time Memory
47456 2018-05-03T09:12:06 Z Just_Solve_The_Problem Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 1380 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define random rand() ^ (rand() << 5)

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;

int n, q;
ll d[N];
pair < ll, ll > ar[N];
ll pos[N];
bool fl = 1;

void solve1() {
  while (q--) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    int tl = -n + t;
    int tr = t;
    int ans = 0;
    if (tl <= l && r <= tr) {
      ans = r - l + 1;
    } else if (l <= tl && tr <= r) {
      ans = tr - tl + 1;
    } else if (tr >= l && l > tl) {
      ans = tr - l + 1;
    } else if (tl <= r && tr > r) {
      ans = r - tl + 1;
    }
    printf("%d\n", ans);
  }
}

void solve2() {
  ar[0] = {1, 1};
  for (int i = 1; i <= n; i++) {
    ar[i].sc = (d[i] + ar[i - 1].sc - 1) / ar[i - 1].sc * ar[i - 1].fr;
    ar[i].fr = (ar[i].sc / ar[i - 1].fr * ar[i - 1].sc + (-(i - 1))) - 1 - (-i);
  }
  while (q--) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    for (int i = 0; i <= n; i++) {
      pos[i] = t / ar[i].sc * ar[i].fr + (-i);
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
      if (pos[i] >= l && pos[i] <= r) {
        ans++;
      }
    }
    printf("%d\n", ans);
  }
}

ll getpos(int in, ll t) {
  return t / ar[in].sc * ar[in].fr + (-in);
}

int getans(ll t, ll L, ll R) {
  int l = 0;
  int r = n;
  int tl, tr;
  if (getpos(0, t) < L) return 0;
  if (getpos(n, t) > R) return 0;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (getpos(mid, t) <= R) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (getpos(l, t) <= R) {
    r = l;
  }
  if (getpos(r, t) < L) {
    return 0;
  }
  tl = r;
  l = 0;
  r = n;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (getpos(mid, t) >= L) {
      l = mid;
    } else {
      r = mid;
    }
  }
  if (getpos(r, t) >= L) {
    l = r;
  }
  if (getpos(l, t) > R) {
    return 0;
  }
  tr = l;
  return abs(tr - tl) + 1;
}

void solve3() {
  ar[0] = {1, 1};
  for (int i = 1; i <= n; i++) {
    ar[i].sc = (d[i] + ar[i - 1].sc - 1) / ar[i - 1].sc * ar[i - 1].fr;
    ar[i].fr = (ar[i].sc / ar[i - 1].fr * ar[i - 1].sc + (-(i - 1))) - 1 - (-i);
  }
  while (q--) {
    ll t, l, r;
    scanf("%lld %lld %lld", &t, &l, &r);
    printf("%d\n", getans(t, l, r));
  }
}

main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &d[i]);
    fl &= (d[i] == 1);
  }
  if (fl) {
    solve1();
  } else if (n <= 1000) {
    solve2();
  } else {
    solve3();
  }
}

Compilation message

worst_reporter3.cpp:128:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
worst_reporter3.cpp: In function 'void solve1()':
worst_reporter3.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &t, &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp: In function 'void solve2()':
worst_reporter3.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &t, &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp: In function 'void solve3()':
worst_reporter3.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &t, &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &d[i]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 7164 KB Output is correct
2 Correct 393 ms 7392 KB Output is correct
3 Correct 411 ms 7436 KB Output is correct
4 Correct 384 ms 7436 KB Output is correct
5 Correct 380 ms 7436 KB Output is correct
6 Correct 382 ms 7436 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7436 KB Output is correct
2 Correct 16 ms 7436 KB Output is correct
3 Correct 16 ms 7436 KB Output is correct
4 Correct 16 ms 7436 KB Output is correct
5 Correct 15 ms 7436 KB Output is correct
6 Correct 17 ms 7436 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 7164 KB Output is correct
2 Correct 393 ms 7392 KB Output is correct
3 Correct 411 ms 7436 KB Output is correct
4 Correct 384 ms 7436 KB Output is correct
5 Correct 380 ms 7436 KB Output is correct
6 Correct 382 ms 7436 KB Output is correct
7 Correct 17 ms 7436 KB Output is correct
8 Correct 16 ms 7436 KB Output is correct
9 Correct 16 ms 7436 KB Output is correct
10 Correct 16 ms 7436 KB Output is correct
11 Correct 15 ms 7436 KB Output is correct
12 Correct 17 ms 7436 KB Output is correct
13 Correct 771 ms 13424 KB Output is correct
14 Correct 777 ms 30064 KB Output is correct
15 Correct 681 ms 45148 KB Output is correct
16 Correct 788 ms 61020 KB Output is correct
17 Correct 1055 ms 80960 KB Output is correct
18 Correct 1046 ms 99628 KB Output is correct
19 Correct 1051 ms 118248 KB Output is correct
20 Correct 1054 ms 136992 KB Output is correct
21 Correct 1022 ms 155732 KB Output is correct
22 Correct 1030 ms 174308 KB Output is correct
23 Correct 998 ms 192860 KB Output is correct
24 Correct 1135 ms 211660 KB Output is correct
25 Correct 1380 ms 227648 KB Output is correct
26 Correct 1377 ms 243100 KB Output is correct
27 Correct 1087 ms 260788 KB Output is correct
28 Correct 1159 ms 262144 KB Output is correct
29 Correct 1063 ms 262144 KB Output is correct
30 Correct 1166 ms 262144 KB Output is correct
31 Correct 1064 ms 262144 KB Output is correct
32 Correct 897 ms 262144 KB Output is correct
33 Correct 2 ms 262144 KB Output is correct