#774184 (C++17) No.924 紲星

提出ソース

結果

問題	No.924 紲星
ユーザー	f1b_maxbl00d
提出日時	2022-06-28 00:18:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	8,142 bytes
コンパイル時間	2,320 ms
コンパイル使用メモリ	166,348 KB
実行使用メモリ	228,928 KB
最終ジャッジ日時	2024-04-30 13:25:08
合計ジャッジ時間	36,747 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	4 ms 6,944 KB
testcase_04	AC	3 ms 6,944 KB
testcase_05	AC	5 ms 6,944 KB
testcase_06	AC	4 ms 6,940 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	AC	1,674 ms 82,972 KB
testcase_14	AC	1,472 ms 44,492 KB
testcase_15	AC	1,473 ms 67,812 KB
testcase_16	AC	1,827 ms 176,212 KB
testcase_17	AC	2,549 ms 79,756 KB
testcase_18	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#pragma warning(disable:4996)
//#include <Windows.h>
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;
template<class T>
using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;

template<class T>
inline void chmin(T& a, T b) {
	a = min(a, b);
}

template<class T>
inline void chmax(T& a, T b) {
	a = max(a, b);
}

//y/xのfloorを求める
LL floor_(LL y, LL x) {
	if (x < 0) {
		x *= -1;
		y *= -1;
	}
	if (y >= 0) {
		return y / x;
	}
	else {
		if ((-y) % x == 0) {
			return y / x;
		}
		else {
			return -((-y) / x) - 1;
		}
	}
}

inline LL mod(LL a, LL m) {
	LL res = a % m;
	return res >= 0 ? res : res + m;
}

void input();
void solve();

void daminput();
void naive();

void outputinput();

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);
	input();
	//daminput();
	solve();
	//naive();
	//outputinput();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////

template<class T>
class CPSegmentTree {
public:
	CPSegmentTree() {}
	void build(int n, function<T(T, T)> tt, T t0)
	{
		TT = tt;
		T0 = t0;
		height = 1;
		//2の累乗化
		int rn = 1;
		while (rn < n)
		{
			rn *= 2;
			height++;
		}
		N = rn;
		ar.resize(2 * N - 1, t0);
		cl.resize(2 * N - 1, -1);
		cr.resize(2 * N - 1, -1);
		time.resize(2 * N - 1, 0);
		for (int n = 0; n < N - 1; n++)
		{
			cl[n] = 2 * n + 1;
			cr[n] = 2 * n + 2;
		}
		roots.push_back(0);
	}
	void build(vector<T>& ar0, function<T(T, T)> tt, T t0)
	{
		TT = tt;
		T0 = t0;
		N = ar0.size();
		int rn = 1;
		while (rn < N)
		{
			rn *= 2;
			height++;
		}
		N = rn;
		cl.resize(2 * N - 1, -1);
		cr.resize(2 * N - 1, -1);
		time.resize(2 * N - 1, 0);
		for (int n = 0; n < N - 1; n++)
		{
			cl[n] = 2 * n + 1;
			cr[n] = 2 * n + 2;
		}
		ar.resize(2 * N - 1, t0);
		for (int n = 0; n < ar0.size(); n++)
		{
			ar[N - 1 + n] = ar0[n];
		}
		for (int n = N - 2; n >= 0; n--)
		{
			ar[n] = TT(ar[cl[n]], ar[cr[n]]);
		}
		roots.push_back(0);
	}
	//時間tの木のコピーを作る この木を表す時間を返す
	//(コピー元の木をこの後いじると壊れる)
	int copy(int t)
	{
		int oldr = roots[t];
		int newt = roots.size();
		roots.push_back(ar.size());
		ar.push_back(ar[oldr]);
		cl.push_back(cl[oldr]);
		cr.push_back(cr[oldr]);
		time.push_back(newt);
		return newt;
	}
	//時間tの頂点nをxに更新
	void set(int t, int n, T x)
	{
		set_node(t, roots[t], 0, N, n, x);
	}
	//時刻tにおける、[l,r)の範囲の積を返す
	T get(int t, int l, int r)
	{
		return get_node(l, r, roots[t], 0, N);
	}
	//時間tにおける、葉nの値
	T get(int t, int n)
	{
		return get(t, n, n + 1);
	}
private:
	//要素数(2の累乗化済み)
	int N;
	//要素
	vector<T> ar;
	//左右の子は何か
	VI cl, cr;
	//積
	function<T(T, T)> TT;
	//単位元
	T T0;
	//時刻tにおける根のid(はじめの時刻は0)
	VI roots;
	//この木の高さ
	int height;
	//各頂点の属する時間
	VI time;
	//時間tの頂点pに対する更新処理
	//範囲[l,r)を持つ
	//更新処理をした結果の自分の頂点番号を返す(新しく時間tに頂点を登録した場合)
	int set_node(int t, int p, int l, int r, int n, T x)
	{
		//頂点pが時間tの頂点でなければ、新しい頂点を作ったうえで変更
		if (time[p] != t)
		{
			int newp = ar.size();
			ar.push_back(ar[p]);
			cl.push_back(cl[p]);
			cr.push_back(cr[p]);
			time.push_back(t);
			p = newp;
		}
		//この頂点が頂点n自身の場合
		if (l == n && r == n + 1)
		{
			ar[p] = x;
			return p;
		}
		//左の子は[l,m)、右の子は[m,r)を持つ
		int m = (r - l) / 2 + l;
		//頂点nが左の子に含まれる場合
		if (n < m)
		{
			cl[p] = set_node(t, cl[p], l, m, n, x);
		}
		//頂点nが右の子に含まれる場合
		else
		{
			cr[p] = set_node(t, cr[p], m, r, n, x);
		}
		ar[p] = TT(ar[cl[p]], ar[cr[p]]);
		return p;
	}
	//再帰用 n:=見る頂点、頂点nの表す範囲は[s,e)
	T get_node(int l, int r, int n, int s, int e)
	{
		if (l <= s && e <= r)
		{
			return ar[n];
		}
		//左の子は[s,m)、右の子は[m,e)を持つ
		int m = (e - s) / 2 + s;
		T res = T0;
		//左の子が[l,r)とかぶる
		if (r > s && m > l)
		{
			res = get_node(l, r, cl[n], s, m);
		}
		//右の子が[l,r)とかぶる
		if (r > m && e > l)
		{
			res = TT(res, get_node(l, r, cr[n], m, e));
		}
		return res;
	}
};

//座圧
class CoordComp
{
public:
	int N;
	VI new2old;
	map<LL, int> old2new;
	CoordComp() :N(0) {};
	//vに含まれる数に昇順で添え字(0-index)を設定する(vは変更しない)
	void build(VLL& v)
	{
		set<LL> all;
		for (LL t : v)
		{
			all.insert(t);
		}
		N = all.size();
		new2old.reserve(N);
		int i = 0;
		for (LL t : all)
		{
			old2new.insert(pair<LL, int>(t, i++));
			new2old.push_back(t);
		}
	}
	//tを圧縮した座標を返す
	LL conv(int t)
	{
		return old2new[t];
	}
	//[l,r)が含む登録点の集合を変換後の座標の区間[s,e)で返す(登録点が存在しなければ[-1,-1)を返す)
	PI conv(LL l, LL r)
	{
		//new2old[s1] < l <= new2old[s2]
		int s1 = -1, s2 = N;
		while (s2 - s1 > 1)
		{
			int m = (s1 + s2) / 2;
			if (new2old[m] < l)
			{
				s1 = m;
			}
			else {
				s2 = m;
			}
		}
		//new2old[e1] < r <= new2old[e2]
		int e1 = -1, e2 = N;
		while (e2 - e1 > 1)
		{
			int m = (e2 + e1) / 2;
			if (new2old[m] < r)
			{
				e1 = m;
			}
			else {
				e2 = m;
			}
		}
		if (s2 >= e2)
		{
			return PI(-1, -1);
		}
		return PI(s2, e2);
	}
	//圧縮済みの座標から、元の数を返す
	LL revconv(int i)
	{
		return new2old[i];
	}
	//登録点の個数
	int size()
	{
		return N;
	}
};

int N, Q;
VLL A;

void input() {
	cin >> N >> Q;
	A.resize(N);
	for (int n = 0; n < N; n++) {
		cin >> A[n];
	}
}

void daminput() {
}

void solve() {
	CoordComp coord;
	coord.build(A);
	CPSegmentTree<int> seg_count;
	seg_count.build(coord.size(), [](int a, int b) {
		return a + b;
	}, 0);
	CPSegmentTree<LL> seg_sum;
	seg_sum.build(coord.size(), [](LL a, LL b) {
		return a + b;
	}, 0);
	for (int n = 0; n < N; n++) {
		int conv = coord.conv(A[n]);
		int old_c = seg_count.get(n, conv);
		seg_count.set(n, conv, old_c + 1);
		LL old_s = seg_sum.get(n, conv);
		seg_sum.set(n, conv, old_s + A[n]);
		seg_count.copy(n);
		seg_sum.copy(n);
	}
	for (int query = 0; query < Q; query++) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		//count[t=l~r][0,s] < (r-l)/2 + 1 <= count[t=l~r][0,e] -> e
		int s = -1, e = coord.size();
		while (e - s > 1) {
			int m = (e + s) / 2;
			int c = seg_count.get(r, 0, m + 1);
			if (l - 1 >= 0) {
				c -= seg_count.get(l - 1, 0, m + 1);
			}
			if (c < (r - l) / 2 + 1) {
				s = m;
			}
			else {
				e = m;
			}
		}
		int p = seg_count.get(r, 0, e + 1);
		if (l - 1 >= 0) {
			p -= seg_count.get(l - 1, 0, e + 1);
		}
		int q = (r-l+1) - p;
		LL x = coord.revconv(e);
		LL ans = x * p;
		ans -= seg_sum.get(r, 0, e + 1);
		if (l - 1 >= 0) {
			ans += seg_sum.get(l - 1, 0, e + 1);
		}
		ans -= x * q;
		ans += seg_sum.get(r, e + 1, coord.size());
		if (l - 1 >= 0) {
			ans -= seg_sum.get(l - 1, e + 1, coord.size());
		}
		cout << ans << "\n";
	}
}

void naive() {
}

void outputinput() {
}

yukicoder

結果

テストケース

ソースコード