oj.uz

Submission #47924

# Submission time Handle Problem Language Result Execution time Memory
47924 2018-05-09T06:45:40 Z duckmoon99 Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 13176 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector < pair<ll, ll> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll d[511111];
ll t[511111];
ll mov[511111];

int main()
{
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL);
	//freopen("stress.txt","w",stdout);
	ll n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> d[i];
	}
	t[0]=d[0];
	mov[0]=d[0];
	//cout << d[0] << " " << d[0] << endl;
	for(int i = 1; i < n; i++){
		ll x = ((d[i]+mov[i-1]-1)/mov[i-1]);
		t[i]=x*t[i-1];
		mov[i]=x*mov[i-1];
		//cout << t[i] << " " << mov[i] << endl;
	}
	ll T, L, R;
	for(int i = 0; i < q; i++){
		cin >> T >> L >> R;
		ll ans = 0;
		for(int j = 0; j < n; j++){
			ll x = -(j+1)+T/t[j]*mov[j];
			if(x<=R && x>=L){
				ans++;
			}
		}
		if(T<=R && T>=L)ans++;
		cout << ans << endl;
		
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 13176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13176 KB Output is correct
2 Correct 16 ms 13176 KB Output is correct
3 Correct 16 ms 13176 KB Output is correct
4 Correct 25 ms 13176 KB Output is correct
5 Correct 17 ms 13176 KB Output is correct
6 Correct 17 ms 13176 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 13176 KB Time limit exceeded
2 Halted 0 ms 0 KB -