oj.uz

Submission #145788

# Submission time Handle Problem Language Result Execution time Memory
145788 2019-08-21T06:54:10 Z maruii 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 9264 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] / 400, 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 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 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 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 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 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 276 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 15 ms 504 KB Output is correct
5 Correct 33 ms 632 KB Output is correct
6 Correct 49 ms 840 KB Output is correct
7 Correct 58 ms 760 KB Output is correct
8 Correct 33 ms 760 KB Output is correct
9 Correct 35 ms 760 KB Output is correct
10 Correct 89 ms 888 KB Output is correct
11 Correct 90 ms 888 KB Output is correct
12 Correct 87 ms 860 KB Output is correct
13 Correct 94 ms 1016 KB Output is correct
14 Correct 78 ms 888 KB Output is correct
15 Correct 85 ms 888 KB Output is correct
16 Correct 36 ms 888 KB Output is correct
17 Correct 13 ms 888 KB Output is correct
18 Correct 82 ms 888 KB Output is correct
19 Correct 92 ms 1016 KB Output is correct
20 Correct 104 ms 888 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 352 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 12 ms 632 KB Output is correct
9 Correct 30 ms 1016 KB Output is correct
10 Correct 11 ms 1148 KB Output is correct
11 Correct 74 ms 6700 KB Output is correct
12 Correct 78 ms 2040 KB Output is correct
13 Correct 132 ms 3544 KB Output is correct
14 Correct 163 ms 6276 KB Output is correct
15 Correct 182 ms 9264 KB Output is correct
16 Correct 100 ms 7336 KB Output is correct
17 Correct 42 ms 3224 KB Output is correct
18 Correct 69 ms 6432 KB Output is correct
19 Correct 91 ms 9132 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 88 ms 1272 KB Output is correct
2 Correct 391 ms 1980 KB Output is correct
3 Correct 949 ms 2836 KB Output is correct
4 Correct 1555 ms 3744 KB Output is correct
5 Correct 2301 ms 4616 KB Output is correct
6 Correct 2570 ms 5340 KB Output is correct
7 Correct 2237 ms 6072 KB Output is correct
8 Correct 1436 ms 7084 KB Output is correct
9 Correct 741 ms 7844 KB Output is correct
10 Correct 295 ms 7996 KB Output is correct
11 Correct 1135 ms 8104 KB Output is correct
12 Correct 3560 ms 8304 KB Output is correct
13 Execution timed out 4054 ms 7264 KB Time limit exceeded
14 Halted 0 ms 0 KB -