oj.uz

Submission #145797

# Submission time Handle Problem Language Result Execution time Memory
145797 2019-08-21T06:59:47 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] / 666, 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 380 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 2 ms 436 KB Output is correct
9 Correct 2 ms 380 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 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 10 ms 376 KB Output is correct
4 Correct 23 ms 508 KB Output is correct
5 Correct 51 ms 632 KB Output is correct
6 Correct 74 ms 760 KB Output is correct
7 Correct 91 ms 888 KB Output is correct
8 Correct 48 ms 760 KB Output is correct
9 Correct 53 ms 760 KB Output is correct
10 Correct 141 ms 872 KB Output is correct
11 Correct 136 ms 856 KB Output is correct
12 Correct 136 ms 888 KB Output is correct
13 Correct 131 ms 1016 KB Output is correct
14 Correct 122 ms 840 KB Output is correct
15 Correct 131 ms 852 KB Output is correct
16 Correct 56 ms 888 KB Output is correct
17 Correct 18 ms 888 KB Output is correct
18 Correct 126 ms 860 KB Output is correct
19 Correct 145 ms 888 KB Output is correct
20 Correct 151 ms 932 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 3 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 380 KB Output is correct
7 Correct 7 ms 508 KB Output is correct
8 Correct 12 ms 696 KB Output is correct
9 Correct 30 ms 1016 KB Output is correct
10 Correct 11 ms 1272 KB Output is correct
11 Correct 74 ms 6608 KB Output is correct
12 Correct 77 ms 2076 KB Output is correct
13 Correct 132 ms 3576 KB Output is correct
14 Correct 175 ms 6464 KB Output is correct
15 Correct 177 ms 9312 KB Output is correct
16 Correct 98 ms 7464 KB Output is correct
17 Correct 42 ms 3092 KB Output is correct
18 Correct 75 ms 6432 KB Output is correct
19 Correct 89 ms 9160 KB Output is correct
20 Correct 52 ms 5496 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 1268 KB Output is correct
2 Correct 534 ms 1980 KB Output is correct
3 Correct 1174 ms 2872 KB Output is correct
4 Correct 1863 ms 3700 KB Output is correct
5 Correct 2572 ms 4480 KB Output is correct
6 Correct 2821 ms 5344 KB Output is correct
7 Correct 2362 ms 6028 KB Output is correct
8 Correct 1452 ms 7020 KB Output is correct
9 Correct 739 ms 7856 KB Output is correct
10 Correct 302 ms 7892 KB Output is correct
11 Correct 1053 ms 8068 KB Output is correct
12 Correct 3419 ms 8180 KB Output is correct
13 Execution timed out 4080 ms 7284 KB Time limit exceeded
14 Halted 0 ms 0 KB -