oj.uz

Submission #772961

# Submission time Handle Problem Language Result Execution time Memory
772961 2023-07-04T13:31:06 Z LucaIlie Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 20376 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++ ) {
        per[i] = higher( per[pos], d[i] );
        if ( d[i] > maxx ) {
            periods.push_back( { per[pos], pos, i - 1 } );
            maxx = d[i];
            pos = i;
        }
        if ( per[i] > MAX_T )
            break;
    }
    periods.push_back( { per[pos], pos, n } );


    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 1054 ms 11124 KB Output is correct
2 Correct 1059 ms 11032 KB Output is correct
3 Correct 1069 ms 11088 KB Output is correct
4 Correct 1109 ms 11108 KB Output is correct
5 Correct 1077 ms 11168 KB Output is correct
6 Correct 1061 ms 11020 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 11124 KB Output is correct
2 Correct 1059 ms 11032 KB Output is correct
3 Correct 1069 ms 11088 KB Output is correct
4 Correct 1109 ms 11108 KB Output is correct
5 Correct 1077 ms 11168 KB Output is correct
6 Correct 1061 ms 11020 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 1068 ms 9596 KB Output is correct
14 Correct 1114 ms 9084 KB Output is correct
15 Correct 1004 ms 9384 KB Output is correct
16 Correct 1089 ms 9440 KB Output is correct
17 Execution timed out 2071 ms 20376 KB Time limit exceeded
18 Halted 0 ms 0 KB -