oj.uz

Submission #772973

# Submission time Handle Problem Language Result Execution time Memory
772973 2023-07-04T13:34:52 Z LucaIlie Worst Reporter 3 (JOI18_worst_reporter3) C++17
7 / 100
 1064 ms 11144 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

struct period {
    int per, l, r;
};

const int MAX_N = 5e5 + 1;
const int MAX_T = 2e9;
int d[MAX_N], per[MAX_N];

int higher( int x, int n ) {
    return ((int)ceil( (double)n / x )) * x;
}

int lower( int x, int n ) {
    return ((int)floor( (double)n / x )) * x;
}

vector<period> periods;

signed main() {
    int n, q;

    cin >> n >> q;
    d[0] = 1;
    for ( int i = 1; i <= n; i++ )
        cin >> d[i];

    int maxx = 1, pos = 0;
    per[0] = 1;
    for ( int i = 1; i <= n; i++ ) {
        if ( d[i] > maxx ) {
            periods.push_back( { per[pos], pos, i - 1 } );
            maxx = d[i];
            pos = i;
        }
        per[i] = higher( per[pos], d[i] );
        if ( periods.size() > 40 || per[i] > MAX_T )
            break;
    }
    if ( per[pos] <= MAX_T )
        periods.push_back( { per[pos], pos, n } );
    if ( periods.size() > 42 )
        return 1;

    while ( q-- ) {
        int t, l, r, ans = 0;
        cin >> t >> l >> r;
        for ( period p: periods ) {
            int lp = lower( p.per, t ) - p.r, rp = lower( p.per, t ) - p.l;
            ans += max( 0LL, min( rp, r ) - max( lp, l ) + 1 );
        }
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 11040 KB Output is correct
2 Correct 1058 ms 11040 KB Output is correct
3 Correct 1022 ms 11044 KB Output is correct
4 Correct 1064 ms 11012 KB Output is correct
5 Correct 1038 ms 11144 KB Output is correct
6 Correct 1012 ms 11124 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 11040 KB Output is correct
2 Correct 1058 ms 11040 KB Output is correct
3 Correct 1022 ms 11044 KB Output is correct
4 Correct 1064 ms 11012 KB Output is correct
5 Correct 1038 ms 11144 KB Output is correct
6 Correct 1012 ms 11124 KB Output is correct
7 Incorrect 2 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -