結果

問題 No.924 紲星
コンテスト
ユーザー ats5515
提出日時 2019-11-08 22:17:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 2,098 bytes
コンパイル時間 1,979 ms
コンパイル使用メモリ 102,500 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2024-09-15 01:34:59
合計ジャッジ時間 9,214 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other AC * 1 RE * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int rem(long long int)’:
main.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
   46 | }
      | ^
main.cpp: In function ‘long long int add(long long int)’:
main.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int BB = 500;
struct Seg {
	int L;
	int R;
	int idx;
	bool operator<(const Seg &right)const {
		if (L / BB == right.L / BB) {
			return R < right.R;
		}
		else {
			return L < right.L;
		}
	}
};

vector<int> A;
vector<pair<int, int> > B;
set<int> st;
int center;
int sum;
int k;
int rem(int i) {
	if (center > i) {
		k--;
	}
	if (center >= i) {
		sum += A[B[i].second];
	}
	else {
		sum -= A[B[i].second];

	}
	st.erase(i);
}

int add(int i) {
	if (center > i) {
		k++;
		sum -= A[B[i].second];
	}
	else {
		sum += A[B[i].second];
	}
	st.insert(i);
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q;
	A.resize(N);
	B.resize(N);
	vector<int> res(Q);
	vector<int> C(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i].first = A[i];
		B[i].second = i;
	}
	sort(B.begin(), B.end());
	for (int i = 0; i < N; i++) {
		C[B[i].second] = i;
	}
	vector<Seg> seg(Q);
	for (int i = 0; i < Q; i++) {
		cin >> seg[i].L >> seg[i].R;
		seg[i].L--;
		seg[i].R--;
		seg[i].idx = i;
	}
	sort(seg.begin(), seg.end());
	int L = 0;
	int R = 0;
	st.insert(C[0]);
	center = C[0];
	sum = -A[0];
	auto s = st.begin();
	for (int i = 0; i < Q; i++) {

		while (L > seg[i].L) {
			L--;
			add(C[L]);
		}
		while (R < seg[i].R) {
			R++;
			add(C[R]);
		}
		while (L < seg[i].L) {
			rem(C[L]);
			L++;
		}
		while (R > seg[i].R) {
			rem(C[R]);
			R--;
		}
		auto s = st.lower_bound(center);
		if (s == st.end()) {
			--s;
			--k;
		}
		else {
			if ((*s) != center) {
				sum -= 2 * A[B[*s].second];
			}
		}
		while (k > (st.size() - 1) / 2) {
			sum += 2 * A[B[*s].second];
			--s;
			--k;
		}

		while (k < (st.size() - 1) / 2) {
			++s;
			++k;
			sum -= 2 * A[B[*s].second];
		}


		center = (*s);
		//cerr << A[*s] << endl;

		res[seg[i].idx] = A[B[center].second] * (st.size() % 2) + sum;

	}

	for (int i = 0; i < Q; i++) {
		cout << res[i] << endl;
	}
}
0