Submission #727425

#	Time	Username	Problem	Language	Result	Execution time	Memory
727425		model_code	Modern Machine (JOI23_ho_t5)	C++17	100 / 100	1263 ms	245456 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	int BeforeL, BeforeR;
	int AfterL, AfterR;
};

bool operator<(const Node& a1, const Node& a2) {
	if (a1.BeforeL < a2.BeforeL) return true;
	return false;
}

class SegmentTree {
public:
	int mod = 0;
	int size_ = 1;
	int tmp = 0;
	vector<vector<Node>> dat;

	// Initialize SegmentTree
	void Init(int sz, int mod_) {
		mod = mod_;
		while (size_ <= sz) size_ *= 2;
		Node ZERO = Node{ 0, mod - 1, 0, mod - 1 };
		dat.resize(size_ * 2, vector<Node>{});
		for (int i = size_; i < size_ * 2; i++) dat[i].push_back(ZERO);
	}

	// Add Information: A[pos] = x
	void update(int pos, int x) {
		pos += size_;
		dat[pos].clear();
		dat[pos].push_back(Node{ 0, x - 1, (x + 1) % mod, (2 * x) % mod });
		dat[pos].push_back(Node{ x, mod - 1, (2 * x) % mod, (mod - 1 + x) % mod });
	}

	// Merge Vertex pos*2 and pos*2+1
	void Merge(int pos) {
		for (int i = 0; i < dat[pos * 2].size(); i++) {
			int pos1 = lower_bound(dat[pos * 2 + 1].begin(), dat[pos * 2 + 1].end(), Node{ dat[pos * 2][i].AfterL + 1, 0, 0, 0 }) - dat[pos * 2 + 1].begin(); pos1--;
			int pos2 = lower_bound(dat[pos * 2 + 1].begin(), dat[pos * 2 + 1].end(), Node{ dat[pos * 2][i].AfterR + 1, 0, 0, 0 }) - dat[pos * 2 + 1].begin(); pos2--;
			if (dat[pos * 2][i].AfterL > dat[pos * 2][i].AfterR) pos2 += dat[pos * 2 + 1].size();

			// Addition
			for (int j = pos1; j <= pos2; j++) {
				int idx = j % dat[pos * 2 + 1].size();
				int cl = dat[pos * 2][i].AfterL;
				int cr = dat[pos * 2][i].AfterR;
				if (cl > cr) {
					if (j >= dat[pos * 2 + 1].size()) cl = 0;
					else cr = mod - 1;
				}

				// Calculate Actual cl, cr & Offset
				cl = max(cl, dat[pos * 2 + 1][idx].BeforeL);
				cr = min(cr, dat[pos * 2 + 1][idx].BeforeR);
				int offset1 = (dat[pos * 2][i].BeforeL - dat[pos * 2][i].AfterL); if (offset1 < 0) offset1 += mod;
				int offset2 = (dat[pos * 2 + 1][idx].AfterL - dat[pos * 2 + 1][idx].BeforeL); if (offset2 < 0) offset2 += mod;

				// Add to dat[pos]
				dat[pos].push_back(Node{ (offset1 + cl) % mod, (offset1 + cr) % mod, (offset2 + cl) % mod, (offset2 + cr) % mod });
			}
		}
	}

	// Recursion
	void query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) {
			int pos1 = lower_bound(dat[u].begin(), dat[u].end(), Node{ tmp + 1, 0, 0, 0 }) - dat[u].begin(); pos1--;
			int offset = dat[u][pos1].AfterL - dat[u][pos1].BeforeL; if (offset < 0) offset += mod;
			tmp = (tmp + offset) % mod;
			return;
		}
		if (r <= a || b <= l) return;
		query_(l, r, a, ((a + b) >> 1), u * 2);
		query_(l, r, ((a + b) >> 1), b, u * 2 + 1);
	}

	// Answer Query [cl, cr)
	int query(int cl, int cr, int x) {
		tmp = x;
		query_(cl, cr, 0, size_, 1);
		return tmp;
	}
};

// Input
int N; char C[120009];
int M, A[120009];
int Q, L[120009], R[120009];
int LeftPos[120009], NumLeft;
int RigtPos[120009], NumRigt;
int NextQ[22][22][120009], Haba[22], UpLimit;
long long SumLeft[22][120009];
long long SumRigt[22][120009];
long long SumRed[120009];
SegmentTree Z;

// Initializing
void Initialize() {
	for (int i = 1; i <= N; i++) {
		if (C[i] == 'B') { NumLeft += 1; LeftPos[NumLeft] = i; }
		if (C[i] == 'R') { NumRigt += 1; RigtPos[NumRigt] = i; }
	}
	LeftPos[0] = 0; LeftPos[NumLeft + 1] = N + 1;
	RigtPos[0] = 0; RigtPos[NumRigt + 1] = N + 1;
	reverse(RigtPos, RigtPos + NumRigt + 2);

	// Calculate NextQ
	while ((1 << UpLimit) < N / 2) UpLimit += 1;
	for (int i = 1; i <= UpLimit; i++) {
		Haba[i] = (1 << (i - 1));
	}
	for (int i = 0; i <= UpLimit; i++) {
		for (int j = 0; j <= UpLimit; j++) {
			NextQ[i][j][M + 1] = M + 1;
			for (int k = M; k >= 0; k--) {
				NextQ[i][j][k] = NextQ[i][j][k + 1];
				if (Haba[i] < A[k] && A[k] <= N - Haba[j] && (C[N] == 'R' || A[k] != N)) NextQ[i][j][k] = k; // Changed from uso1_e869120.cpp
			}
		}
	}

	// Calculate Cumulative Sum
	for (int i = 0; i <= UpLimit; i++) {
		SumLeft[i][0] = 0;
		SumRigt[i][0] = 0;
		for (int j = 1; j <= M; j++) {
			SumLeft[i][j] = SumLeft[i][j - 1]; if (A[j] <= Haba[i]) SumLeft[i][j] += A[j];
			SumRigt[i][j] = SumRigt[i][j - 1]; if (N - Haba[i] < A[j]) SumRigt[i][j] += (N - A[j]);
		}
	}
	for (int i = 1; i <= N; i++) {
		SumRed[i] = SumRed[i - 1];
		if (C[i] == 'R') SumRed[i] += 1;
	}
}

// Get number of 'R's when putting ball at place pos
int GetNumR(int cl, int cr, int pos) {
	int val = LeftPos[cl] + (SumRed[RigtPos[cr] - 1] - SumRed[LeftPos[cl]]);
	if (pos != -1) {
		val += pos;
		if (RigtPos[cr] <= pos || (LeftPos[cl] < pos && C[pos] == 'B')) val += 1;
		val %= (N + 1);
	}
	return val;
}

// Answer query [bl, br]
int solve(int bl, int br) {
	int IndexL = 0, LeftLevel = 0;
	int IndexR = 0, RigtLevel = 0;
	int CurrentButton = bl;

	// Repeat Binary Search
	while (true) {
		int Target = min(br + 1, NextQ[LeftLevel][RigtLevel][CurrentButton]);

		// Binary Search
		if (CurrentButton < Target) {
			int cl = CurrentButton, cm, cr = Target;
			int maxn = CurrentButton - 1;
			int maxL = IndexL;
			int maxR = IndexR;
			for (int i = 0; i < 22; i++) {
				cm = (cl + cr) / 2;
				int pos1 = min((long long)NumLeft + 1, IndexL + SumLeft[LeftLevel][cm] - SumLeft[LeftLevel][CurrentButton - 1]);
				int pos2 = min((long long)NumRigt + 1, IndexR + SumRigt[RigtLevel][cm] - SumRigt[RigtLevel][CurrentButton - 1]);
				if (LeftPos[pos1] + 1 < RigtPos[pos2]) {
					if (maxn < cm) { maxn = cm; maxL = pos1; maxR = pos2; }
					cl = cm;
				}
				else {
					cr = cm;
				}
			}

			// When it goes to phase #2
			if (maxn != Target - 1) {
				int StartingPosition = GetNumR(maxL, maxR, A[maxn + 1]);
				return Z.query(maxn + 2, br + 1, StartingPosition);
			}
			CurrentButton = Target;
			IndexL = maxL;
			IndexR = maxR;
		}
		
		// If all query finished
		int CurrentR = GetNumR(IndexL, IndexR, -1);
		if (CurrentButton == br + 1) return CurrentR;

		// Performing "O(1) operation"
		int NewIndexL = IndexL;
		int NewIndexR = IndexR;
		int Change = 0;
		if (RigtPos[IndexR] <= A[CurrentButton] || (LeftPos[IndexL] < A[CurrentButton] && C[A[CurrentButton]] == 'B')) Change = 1;
		if (N - CurrentR >= A[CurrentButton]) NewIndexL += A[CurrentButton] + Change;
		else NewIndexR += (N + 1 - A[CurrentButton]) - Change;

		// When it goes to phase #2
		if (LeftPos[min(NumLeft + 1, NewIndexL)] + 1 >= RigtPos[min(NumRigt + 1, NewIndexR)]) {
			return Z.query(CurrentButton + 1, br + 1, (CurrentR + Change + A[CurrentButton]) % (N + 1));
		}
		IndexR = NewIndexR;
		IndexL = NewIndexL;
		CurrentButton += 1;

		// Update Level
		while (LeftLevel < UpLimit && Haba[LeftLevel + 1] <= LeftPos[IndexL]) LeftLevel += 1;
		while (RigtLevel < UpLimit && Haba[RigtLevel + 1] <= N + 1 - RigtPos[IndexR]) RigtLevel += 1;
	}
}

int main() {
	// Input
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) cin >> C[i];
	for (int i = 1; i <= M; i++) scanf("%d", &A[i]);
	scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);

	// Precount
	Z.Init(M + 2, N + 1);
	for (int i = 1; i <= M; i++) Z.update(i, A[i]);
	for (int i = Z.size_ - 1; i >= 1; i--) Z.Merge(i);
	Initialize();

	// Answer Query
	for (int i = 1; i <= Q; i++) {
		printf("%d\n", solve(L[i], R[i]));
	}
	return 0;
}

Compilation message (stderr)

Main.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning (disable: 4996)
      | 
Main.cpp: In member function 'void SegmentTree::Merge(int)':
Main.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < dat[pos * 2].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:54:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      if (j >= dat[pos * 2 + 1].size()) cl = 0;
      |          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:221:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:223:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |  for (int i = 1; i <= M; i++) scanf("%d", &A[i]);
      |                               ~~~~~^~~~~~~~~~~~~
Main.cpp:224:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:225:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |  for (int i = 1; i <= Q; i++) scanf("%d%d", &L[i], &R[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 26 / 26
• Subtask 6: 17 / 17
• Subtask 7: 21 / 21