oj.uz

Submission #145852

# Submission time Handle Problem Language Result Execution time Memory
145852 2019-08-21T07:17:16 Z maruii 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 8180 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()

int X[100005], in[100005][2];
vector<int> xx;

const int SIZE = 1 << 17;
struct ST {
	long long A[2 * SIZE];
	int sz;
	void update(int x, long long v) {
		x += SIZE; A[x] += v;
		for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
	}
	long long query() { return A[1]; }
} seg;
		
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, Q; cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> X[i], xx.eack(X[i]);
	sort(all(xx));
	xx.erase(unique(all(xx)), xx.end());
	for (int i = 1; i <= N; ++i) {
		X[i] = lower_bound(all(xx), X[i]) - xx.begin();
	}
	seg.sz = xx.size() - 1;
	
	vector<pii> qry[170];
	vector<long long> ans(Q);

	for (int i = 0; i < Q; ++i) {
		cin >> in[i][0] >> in[i][1];
		qry[in[i][0] / 600].eack(in[i][1], i);
	}
	for (int i = 1; i <= N / 600; ++i) sort(all(qry[i]));

	int s = 1, e = 0;
	for (int ii = 0; ii <= N / 600; ++ii) {
		for (auto i : qry[ii]) {
			int ns = in[i.ss][0], ne = in[i.ss][1];	
			for (; s < ns; ++s) seg.update(X[s], -xx[X[s]]);
			for (; s > ns; --s) seg.update(X[s - 1], xx[X[s - 1]]);
			for (; e < ne; ++e) seg.update(X[e + 1], xx[X[e + 1]]);
			for (; e > ne; --e) seg.update(X[e], -xx[X[e]]);
			ans[i.ss] = seg.query();
		}
	}
	
	for (auto i : ans) cout << i << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 33 ms 504 KB Output is correct
5 Correct 77 ms 572 KB Output is correct
6 Correct 125 ms 632 KB Output is correct
7 Correct 120 ms 732 KB Output is correct
8 Correct 129 ms 636 KB Output is correct
9 Correct 128 ms 624 KB Output is correct
10 Correct 126 ms 888 KB Output is correct
11 Correct 120 ms 760 KB Output is correct
12 Correct 118 ms 632 KB Output is correct
13 Correct 118 ms 696 KB Output is correct
14 Correct 119 ms 760 KB Output is correct
15 Correct 121 ms 632 KB Output is correct
16 Correct 128 ms 632 KB Output is correct
17 Correct 151 ms 760 KB Output is correct
18 Correct 120 ms 632 KB Output is correct
19 Correct 115 ms 732 KB Output is correct
20 Correct 120 ms 760 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 9 ms 508 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 632 KB Output is correct
9 Correct 13 ms 888 KB Output is correct
10 Correct 15 ms 1268 KB Output is correct
11 Correct 74 ms 5456 KB Output is correct
12 Correct 35 ms 2040 KB Output is correct
13 Correct 52 ms 3168 KB Output is correct
14 Correct 78 ms 5528 KB Output is correct
15 Correct 107 ms 8180 KB Output is correct
16 Correct 69 ms 6272 KB Output is correct
17 Correct 36 ms 2932 KB Output is correct
18 Correct 59 ms 5592 KB Output is correct
19 Correct 63 ms 7924 KB Output is correct
20 Correct 37 ms 4596 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 888 KB Output is correct
2 Correct 537 ms 1360 KB Output is correct
3 Correct 812 ms 2296 KB Output is correct
4 Correct 1250 ms 3192 KB Output is correct
5 Correct 1682 ms 3960 KB Output is correct
6 Correct 1856 ms 4536 KB Output is correct
7 Correct 2106 ms 5120 KB Output is correct
8 Correct 2711 ms 5996 KB Output is correct
9 Correct 3447 ms 6700 KB Output is correct
10 Execution timed out 4017 ms 5748 KB Time limit exceeded
11 Halted 0 ms 0 KB -