Submission #1066152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066152		phong	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	663 ms	45016 KiB

worst_reporter3

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 5e5 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 7, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, q;
int a[nmax], d[nmax], L[nmax], R[nmax];
int r[nmax];

int get(int u){
    return r[u] ? r[u] = get(r[u]) : u;
}
void Union(int u, int v){
    int x = get(u);
    int y = get(v);
    if(x != y){
        r[x] = y;
        L[y] = min(L[x], L[y]);
        R[y] = max(R[x], R[y]);
    }
}
int b[nmax], c[nmax];
struct node{
    int t, l, r;
}Q[nmax];

vector<int> nen;
ll calc(int t, int m){
    int cur = 1, i = n, kq = 0;
    bool ok = (t <= m);
    t /= d[n];
    int base = 3;
    while(1){
        int tx = get(i);
        int l =L[tx], r = R[tx];
        while(l <= r){
            int mid = r + l >> 1;
            if(a[mid] + (t * (b[mid] - a[mid])) <= m){
                l = mid + 1;
                kq = max(kq, mid);
            }
            else r= mid - 1;
        }
//        cout << a[n - 1] + (t * (b[n - 1] - a[n - 1])) << ' ';
//        cout << c[L[tx]] << ' ';
        i = L[tx] - 1;
        if(i == 0) break;
        t /= c[L[tx]];
        if(!t) break;
    }
    int l = 1, r = i;
    while(l <= r){
        int mid = r+ l >> 1;
        if(a[mid] <= m){
            l = mid + 1;
            kq = max(kq, mid);
        }
        else r = mid -1;
    }
    return kq + ok;

}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)cin >> d[n - i + 1], a[n - i + 1] = -i;
    for(int i = 1; i <= n; ++i) L[i] = R[i] = i;
    b[n] = a[n] + d[n];
    for(int i = n - 1; i >= 1; --i){
        if(a[i] + d[i] < b[i + 1]){
            b[i] = b[i + 1] - 1;
            Union(i, i + 1);
//            cout << i << ' ';
        }
        else {
            int x = b[i + 1] - a[i + 1];
            int l = 2, r = 1e9, kq = -1;
            while(l <= r){
                int mid = r + l >> 1;
                if(a[i] + d[i] < a[i + 1] + (x * mid)){
                    r = mid - 1;
                    kq = mid;
                }
                else l = mid + 1;
            }
            c[i + 1] = kq;
            b[i] = a[i + 1] + (x * kq) - 1;
        }
    }
//    cout << b[2] - a[2] << endl;
//    for(int i = 1; i <= n; ++i) cout << get(i) << ' ';
//    cout << c[3] << ' ' << c[1];
//    calc(100, 100);
//    calc(8, 5);
    for(int e = 1,t,l,r; e <= q; ++e){
        cin >> t >> l >> r;
        cout << calc(t, r) - calc(t, l - 1)<< endl;
    }



}
/*
3 1
2 3 3
8 3 5


*/

Compilation message (stderr)

worst_reporter3.cpp: In function 'long long int calc(long long int, long long int)':
worst_reporter3.cpp:47:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid = r + l >> 1;
      |                       ~~^~~
worst_reporter3.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = r+ l >> 1;
      |                   ~^~~
worst_reporter3.cpp:39:9: warning: unused variable 'cur' [-Wunused-variable]
   39 |     int cur = 1, i = n, kq = 0;
      |         ^~~
worst_reporter3.cpp:42:9: warning: unused variable 'base' [-Wunused-variable]
   42 |     int base = 3;
      |         ^~~~
worst_reporter3.cpp: At global scope:
worst_reporter3.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:92:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 int mid = r + l >> 1;
      |                           ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81