oj.uz

Submission #624995

# Submission time Handle Problem Language Result Execution time Memory
624995 2022-08-09T08:48:20 Z Arnch Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 2000 ms 13148 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int a[N], d[N];
int T[N], L[N], R[N];
map<int, pair<int, int> > s;

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	int n, q; cin >>n >>q;
	for(int i = 1; i <= n; i++) cin >>a[i];

	bool f = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] > 1) f = 1;
	}

	d[1] = a[1];
	for(int i = 2; i <= n; i++) {
		if(a[i] <= a[i - 1]) {
			d[i] = d[i - 1];
			continue;
		}
		ll cnt = a[i] / d[i - 1];
		if(cnt * d[i - 1] < a[i]) cnt++;
		d[i] = d[i - 1] * cnt;
	}

	vector<int> vc;
	for(int i = 1; i <= n;) {
		if(d[i] > 1e9) continue;
		int ptr = i;
		while(ptr <= n && d[ptr] == d[i]) ptr++;
		s[d[i]] = make_pair(i, ptr - 1);
		vc.push_back(d[i]);
		i = ptr;
	}
	sort(All(vc)), vc.erase(unique(All(vc)), vc.end());

	if(f && n > 1000) {
		assert(0);
	}

	for(int j = 0; j < q; j++) {
		cin >>T[j] >>L[j] >>R[j];
		int ans = 0;
		for(auto i : vc) {
			if(i > T[j]) break;
			int cnt = (T[j] / i) * i;
			int l = cnt + -s[i].second, r = cnt + -s[i].first;
			if(r < L[j] || l > R[j]) continue;
			if(r >= R[j] && l <= L[j]) {
				ans += R[j] - L[j] + 1;
				continue;
			}
			if(R[j] >= r && L[j] <= l) {
				ans += r - l + 1;
				continue;
			}
			if(r <= R[j]) ans += r - L[j] + 1;
			else ans += R[j] - l + 1;
		}
		cout<<ans + (T[j] >= L[j] && T[j] <= R[j]) <<endl;
	}
		
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 13076 KB Output is correct
2 Correct 242 ms 13148 KB Output is correct
3 Correct 203 ms 13096 KB Output is correct
4 Correct 227 ms 13136 KB Output is correct
5 Correct 209 ms 13056 KB Output is correct
6 Correct 203 ms 13072 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 13076 KB Output is correct
2 Correct 242 ms 13148 KB Output is correct
3 Correct 203 ms 13096 KB Output is correct
4 Correct 227 ms 13136 KB Output is correct
5 Correct 209 ms 13056 KB Output is correct
6 Correct 203 ms 13072 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Execution timed out 2052 ms 4124 KB Time limit exceeded
14 Halted 0 ms 0 KB -