oj.uz

Submission #399915

# Submission time Handle Problem Language Result Execution time Memory
399915 2021-05-06T22:49:01 Z GioChkhaidze Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 2000 ms 6504 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 5e5 + 5;

int n, q, d[N];
vector < pair < int , int > > v;
 
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		if (!v.size() || d[v.back().f] < d[i]) {
			v.pb({i, 1});
		}
			else {
			++v.back().s;		
		}
	}
	
	ll x = 1;
	for (int i = 0; i < v.size(); ++i) {
		v[i].f = x * ((d[v[i].f] - 1) / x + 1);
		x = v[i].f;
	}
	
	if (v.size() > 60) {
		x += 1/0;
	}
	
	int t, l, r, sum, ans, L, R;
	for (int i = 1; i <= q; ++i) {
		cin >> t >> l >> r;
		if (t < l) {
			cout << 0 << "\n";
			continue;
		}
		
		sum = -1, ans = (l <= t && t <= r);
		for (int j = 0; j < v.size(); ++j) {
			R = t + (sum - t % v[j].f);
			L = R - v[j].s + 1;	
			if (R < l) break;
			ans += max(0, min(R, r) - max(L, l) + 1);
			sum -= v[j].s;
		}
		
		cout << ans << "\n";
	}
}

Compilation message

worst_reporter3.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main () {
      |       ^
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
worst_reporter3.cpp:39:9: warning: division by zero [-Wdiv-by-zero]
   39 |   x += 1/0;
      |        ~^~
worst_reporter3.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = 0; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 5552 KB Output is correct
2 Correct 257 ms 5528 KB Output is correct
3 Correct 263 ms 5512 KB Output is correct
4 Correct 249 ms 5436 KB Output is correct
5 Correct 259 ms 5516 KB Output is correct
6 Correct 255 ms 5484 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 5552 KB Output is correct
2 Correct 257 ms 5528 KB Output is correct
3 Correct 263 ms 5512 KB Output is correct
4 Correct 249 ms 5436 KB Output is correct
5 Correct 259 ms 5516 KB Output is correct
6 Correct 255 ms 5484 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 250 ms 3500 KB Output is correct
14 Correct 261 ms 3440 KB Output is correct
15 Correct 237 ms 3528 KB Output is correct
16 Correct 254 ms 3524 KB Output is correct
17 Execution timed out 2076 ms 6504 KB Time limit exceeded
18 Halted 0 ms 0 KB -