oj.uz

답안 #145820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145820 2019-08-21T07:05:00 Z maruii 역사적 조사 (JOI14_historical) C++14
0 / 100
 101 ms 1248 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<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;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 1248 KB Output isn't correct
2 Halted 0 ms 0 KB -