oj.uz

답안 #68827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68827 2018-08-18T17:03:50 Z chpipis Worst Reporter 3 (JOI18_worst_reporter3) C++11
19 / 100
 921 ms 114616 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 5e5 + 5;
const int MAX_STEP = 1e9 + 200;

int d[MAXN], n;
int step[MAXN];

int getcnt(int t, int idx) {
    int lo = 0, hi = n;
    int res = -1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int pos = (t / step[mid]) * step[mid] - mid;
        if (pos <= idx) {
            res = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    if (res == -1)
        return 0;
    return n - res + 1;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &d[i]);
    step[0] = 1;
    step[1] = d[1];
    for (int i = 2; i <= n; i++) {
        int lo = 1, hi = MAX_STEP / step[i - 1];
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (mid * step[i - 1] - (i - 1) + i > d[i])
                hi = mid;
            else
                lo = mid + 1;
        }
        step[i] = hi * step[i - 1];
    }
    while (q--) {
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        printf("%d\n", getcnt(t, r) - getcnt(t, l - 1));
    }
    return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:85:10: 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:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 799 ms 22728 KB Output is correct
2 Correct 825 ms 38340 KB Output is correct
3 Correct 807 ms 53792 KB Output is correct
4 Correct 917 ms 69408 KB Output is correct
5 Correct 921 ms 84832 KB Output is correct
6 Correct 793 ms 100368 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 100368 KB Output is correct
2 Correct 3 ms 100368 KB Output is correct
3 Correct 3 ms 100368 KB Output is correct
4 Correct 3 ms 100368 KB Output is correct
5 Correct 4 ms 100368 KB Output is correct
6 Correct 4 ms 100368 KB Output is correct

Subtask #3
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 799 ms 22728 KB Output is correct
2 Correct 825 ms 38340 KB Output is correct
3 Correct 807 ms 53792 KB Output is correct
4 Correct 917 ms 69408 KB Output is correct
5 Correct 921 ms 84832 KB Output is correct
6 Correct 793 ms 100368 KB Output is correct
7 Correct 4 ms 100368 KB Output is correct
8 Correct 3 ms 100368 KB Output is correct
9 Correct 3 ms 100368 KB Output is correct
10 Correct 3 ms 100368 KB Output is correct
11 Correct 4 ms 100368 KB Output is correct
12 Correct 4 ms 100368 KB Output is correct
13 Incorrect 578 ms 114616 KB Output isn't correct
14 Halted 0 ms 0 KB -