oj.uz

Submission #145791

# Submission time Handle Problem Language Result Execution time Memory
145791 2019-08-21T06:55:58 Z maruii 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 9304 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] / 800, 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 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 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 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 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 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 11 ms 504 KB Output is correct
4 Correct 27 ms 504 KB Output is correct
5 Correct 63 ms 764 KB Output is correct
6 Correct 86 ms 764 KB Output is correct
7 Correct 108 ms 760 KB Output is correct
8 Correct 58 ms 760 KB Output is correct
9 Correct 63 ms 760 KB Output is correct
10 Correct 168 ms 888 KB Output is correct
11 Correct 163 ms 852 KB Output is correct
12 Correct 161 ms 852 KB Output is correct
13 Correct 164 ms 1016 KB Output is correct
14 Correct 140 ms 880 KB Output is correct
15 Correct 158 ms 888 KB Output is correct
16 Correct 68 ms 868 KB Output is correct
17 Correct 20 ms 888 KB Output is correct
18 Correct 150 ms 876 KB Output is correct
19 Correct 168 ms 888 KB Output is correct
20 Correct 174 ms 1016 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 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 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 13 ms 760 KB Output is correct
9 Correct 30 ms 1144 KB Output is correct
10 Correct 12 ms 1272 KB Output is correct
11 Correct 74 ms 6732 KB Output is correct
12 Correct 77 ms 2036 KB Output is correct
13 Correct 132 ms 3572 KB Output is correct
14 Correct 158 ms 6440 KB Output is correct
15 Correct 178 ms 9304 KB Output is correct
16 Correct 98 ms 7336 KB Output is correct
17 Correct 41 ms 3092 KB Output is correct
18 Correct 68 ms 6460 KB Output is correct
19 Correct 90 ms 9288 KB Output is correct
20 Correct 52 ms 5492 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1272 KB Output is correct
2 Correct 621 ms 1984 KB Output is correct
3 Correct 1341 ms 2964 KB Output is correct
4 Correct 2090 ms 3704 KB Output is correct
5 Correct 2859 ms 4524 KB Output is correct
6 Correct 3114 ms 5336 KB Output is correct
7 Correct 2570 ms 6024 KB Output is correct
8 Correct 1554 ms 7120 KB Output is correct
9 Correct 724 ms 7896 KB Output is correct
10 Correct 306 ms 8032 KB Output is correct
11 Correct 1115 ms 8160 KB Output is correct
12 Correct 3568 ms 8176 KB Output is correct
13 Execution timed out 4017 ms 7260 KB Time limit exceeded
14 Halted 0 ms 0 KB -