| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 772958 | LucaIlie | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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( 0, min( rp, r ) - max( lp, l ) + 1 );
}
cout << ans << "\n";
}
return 0;
}