oj.uz

Submission #242210

# Submission time Handle Problem Language Result Execution time Memory
242210 2020-06-27T05:54:02 Z shenxy Worst Reporter 3 (JOI18_worst_reporter3) C++11
19 / 100
 2000 ms 62072 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> jmp;
typedef pair<ii, ii> q;
struct seg {
	int s, e, m, minv, lazy;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e, m = (s + e) / 2, minv = -e, lazy = 0;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
		}
	}
	void prop() {
		if (lazy != 0) {
			minv += lazy;
			if (s != e) {
				l -> lazy += lazy;
				r -> lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, int dv) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, dv);
			else if (b <= m) l -> update(a, b, dv);
			else l -> update(a, m, dv), r -> update(m + 1, b, dv);
			l -> prop(), r -> prop();
			minv = min(l -> minv, r -> minv);
		} else lazy += dv;
	}
	int lidx(int i) {
		if (s != e) {
			l -> prop(), r -> prop();
			if (l -> minv <= i) return l -> lidx(i);
			else if (r -> minv <= i) return r -> lidx(i);
			else return e + 1;
		} else return s;
	}
} *root;
int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	int D[N], T, L, R, ans[Q];
	q queries[Q];
	for (int i = 0; i < N; ++i) scanf("%d", &D[i]);
	for (int i = 0; i < Q; ++i) {
		scanf("%d %d %d", &T, &L, &R);
		queries[i] = q(ii(T, i), ii(L, R));
	}
	sort(queries, queries + Q);
	vector<jmp> jumps;
	int j = 1, l = 0;
	for (int i = 0; i < N; ++i) {
		if (D[i] > j) {
			jumps.push_back(jmp(j, ii(l, i)));
			j = j * ((D[i] + j - 1) / j);
			l = i + 1;
		}
	}
	jumps.push_back(jmp(j, ii(l, N)));
	root = new seg(0, N);
	T = 0;
	for (q i: queries) {
		for (jmp j: jumps) root -> update(j.S.F, j.S.S, j.F * (i.F.F / j.F - T / j.F));
		root -> prop();
		ans[i.F.S] = root -> lidx(i.S.F - 1) - root -> lidx(i.S.S);
		T = i.F.F;
	}
	for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:53:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d", &D[i]);
                              ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &T, &L, &R);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 62048 KB Output is correct
2 Correct 1246 ms 62072 KB Output is correct
3 Correct 1217 ms 62072 KB Output is correct
4 Correct 1348 ms 62072 KB Output is correct
5 Correct 1215 ms 62072 KB Output is correct
6 Correct 1403 ms 62072 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 62048 KB Output is correct
2 Correct 1246 ms 62072 KB Output is correct
3 Correct 1217 ms 62072 KB Output is correct
4 Correct 1348 ms 62072 KB Output is correct
5 Correct 1215 ms 62072 KB Output is correct
6 Correct 1403 ms 62072 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 729 ms 60152 KB Output is correct
14 Correct 716 ms 60024 KB Output is correct
15 Correct 673 ms 59896 KB Output is correct
16 Correct 704 ms 60024 KB Output is correct
17 Execution timed out 2091 ms 59000 KB Time limit exceeded
18 Halted 0 ms 0 KB -