oj.uz

Submission #484071

# Submission time Handle Problem Language Result Execution time Memory
484071 2021-11-02T05:11:19 Z xiaowuc1 Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 856 ms 29176 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void solve() {
  int n, q;
  cin >> n >> q;
  vector<ll> slows(n+1);
  slows[0] = 1;
  for(int i = 1; i <= n; i++) cin >> slows[i];
  vector<ll> actual(n+1, 1);
  auto eval = [&](int idx, ll t) {
    ll interval = t / actual[idx];
    return interval * actual[idx] - idx;
  };
  auto getamt = [&](ll rhs, ll t) {
    // how many are <= rhs
    if(eval(n, t) > rhs) return 0;
    int a = 0;
    int b = n;
    while(a < b) {
      int mid = (a+b)/2;
      if(eval(mid, t) > rhs) a = mid+1;
      else b = mid;
    }
    return n+1-a;
  };
  for(int i = 1; i <= n; i++) {
    ll lhs = slows[i-1];
    ll rhs = 1e18;
    while(lhs < rhs) {
      ll mid = (lhs+rhs)/2;
      if(eval(i-1, mid) - (-i) > slows[i]) rhs = mid;
      else lhs = mid+1;
    }
    actual[i] = lhs;
  }
  while(q--) {
    ll t, lloc, rloc;
    cin >> t >> lloc >> rloc;
    cout << getamt(rloc, t) - getamt(lloc-1, t) << "\n";
  }
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 26588 KB Output is correct
2 Correct 856 ms 26588 KB Output is correct
3 Correct 809 ms 26556 KB Output is correct
4 Correct 779 ms 26568 KB Output is correct
5 Correct 772 ms 26604 KB Output is correct
6 Correct 761 ms 26552 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 26588 KB Output is correct
2 Correct 856 ms 26588 KB Output is correct
3 Correct 809 ms 26556 KB Output is correct
4 Correct 779 ms 26568 KB Output is correct
5 Correct 772 ms 26604 KB Output is correct
6 Correct 761 ms 26552 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 536 ms 25032 KB Output is correct
14 Correct 525 ms 25588 KB Output is correct
15 Correct 572 ms 24288 KB Output is correct
16 Correct 546 ms 24976 KB Output is correct
17 Correct 584 ms 29088 KB Output is correct
18 Correct 590 ms 29064 KB Output is correct
19 Correct 591 ms 29108 KB Output is correct
20 Correct 658 ms 29132 KB Output is correct
21 Correct 636 ms 29156 KB Output is correct
22 Correct 601 ms 29176 KB Output is correct
23 Correct 602 ms 29056 KB Output is correct
24 Correct 654 ms 29124 KB Output is correct
25 Correct 820 ms 26624 KB Output is correct
26 Correct 853 ms 26500 KB Output is correct
27 Correct 665 ms 28804 KB Output is correct
28 Correct 656 ms 28964 KB Output is correct
29 Correct 678 ms 28604 KB Output is correct
30 Correct 654 ms 28668 KB Output is correct
31 Correct 677 ms 28856 KB Output is correct
32 Correct 611 ms 25092 KB Output is correct
33 Correct 1 ms 204 KB Output is correct