oj.uz

Submission #145790

# Submission time Handle Problem Language Result Execution time Memory
145790 2019-08-21T06:55:06 Z maruii 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 9312 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 nn, int ns, int ne, int x, int v) {
		if (ns > x || ne < x) return;
		if (x <= ns && ne <= x) {
			A[nn] += v;
			return;
		}
		int m = ns + ne >> 1;
		update(nn << 1, ns, m, x, v);
		update(nn << 1 | 1, m + 1, ne, x, v);
		A[nn] = max(A[nn << 1], A[nn << 1 | 1]);
	}
	void update(int x, int v) { update(1, 0, sz, x, v); }
	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<pair<pii, int> > qry(Q);
	vector<long long> ans(Q);

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

	int s = 1, e = 0;
	for (auto i : qry) {
		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;
}

Compilation message

historic.cpp: In member function 'void ST::update(int, int, int, int, int)':
historic.cpp:22:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~

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 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 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 376 KB Output is correct
14 Correct 2 ms 376 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 396 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 21 ms 504 KB Output is correct
5 Correct 47 ms 632 KB Output is correct
6 Correct 66 ms 840 KB Output is correct
7 Correct 80 ms 888 KB Output is correct
8 Correct 44 ms 760 KB Output is correct
9 Correct 47 ms 760 KB Output is correct
10 Correct 126 ms 880 KB Output is correct
11 Correct 124 ms 880 KB Output is correct
12 Correct 129 ms 888 KB Output is correct
13 Correct 124 ms 988 KB Output is correct
14 Correct 112 ms 884 KB Output is correct
15 Correct 122 ms 844 KB Output is correct
16 Correct 51 ms 888 KB Output is correct
17 Correct 16 ms 888 KB Output is correct
18 Correct 113 ms 940 KB Output is correct
19 Correct 134 ms 888 KB Output is correct
20 Correct 134 ms 888 KB Output is correct

Subtask #3
25.0 / 25.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 3 ms 348 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 12 ms 760 KB Output is correct
9 Correct 32 ms 1076 KB Output is correct
10 Correct 12 ms 1244 KB Output is correct
11 Correct 76 ms 6700 KB Output is correct
12 Correct 77 ms 2164 KB Output is correct
13 Correct 134 ms 3636 KB Output is correct
14 Correct 158 ms 6312 KB Output is correct
15 Correct 178 ms 9312 KB Output is correct
16 Correct 99 ms 7424 KB Output is correct
17 Correct 42 ms 3092 KB Output is correct
18 Correct 68 ms 6460 KB Output is correct
19 Correct 93 ms 9116 KB Output is correct
20 Correct 53 ms 5492 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1244 KB Output is correct
2 Correct 490 ms 1984 KB Output is correct
3 Correct 1103 ms 2868 KB Output is correct
4 Correct 1783 ms 3696 KB Output is correct
5 Correct 2454 ms 4496 KB Output is correct
6 Correct 2722 ms 5344 KB Output is correct
7 Correct 2283 ms 6036 KB Output is correct
8 Correct 1422 ms 7016 KB Output is correct
9 Correct 683 ms 7888 KB Output is correct
10 Correct 288 ms 8032 KB Output is correct
11 Correct 1075 ms 8092 KB Output is correct
12 Correct 3359 ms 8184 KB Output is correct
13 Execution timed out 4005 ms 7264 KB Time limit exceeded
14 Halted 0 ms 0 KB -