Submission #1181710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181710		miniob	Modern Machine (JOI23_ho_t5)	C++20	37 / 100	549 ms	59372 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int gdzie[120007];
int n;
bool debug = false;
bool debug2 = false;

struct przedzial
{
	int l, r, ile;
	bool operator < (przedzial a) const
	{
		return l < a.l;
	}
};

vector<przedzial> drz[262150];

vector<przedzial> lacz_przedzialy(const vector<przedzial>& pierwszy, const vector<przedzial>& drugi)
{
	vector<przedzial> wynik;
	/*przedzial szukane;
	szukane.l = 2;
	szukane.r = 1;
	szukane.ile = 2;*/
	if (pierwszy.size() == 0)
	{
		wynik = drugi;
		return wynik;
	}
	if (drugi.size() == 0)
	{
		wynik = pierwszy;
		return wynik;
	}
	for (auto x : pierwszy)
	{
		int nowel, nower;
		nowel = (x.l + x.ile) % (n + 1);
		nower = (x.r + x.ile) % (n + 1);
		if(debug)
		{
			cout << "nowe: " << nowel << " " << nower << endl;
		}
		if (nowel <= nower)
		{
			przedzial tempo;
			tempo.l = nowel;
			tempo.r = -1;
			auto it = --upper_bound(drugi.begin(), drugi.end(), tempo);
			/*if (it != drugi.begin())
			{
				it--;
			}*/
			if(debug)
			{
				cout << "wyw  " << nowel << " " << nower << " " << x.ile << endl;
			}
			while (it != drugi.end() && nowel <= nower)
			{
				if(debug)
				{
					cout << "cur " << nowel << " " << nower << endl;
					cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
				}
				int nowel2 = max(nowel, it->l);
				int nower2 = min(nower, it->r);
				nowel = nower2 + 1;
				if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
				{
					wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
				}
				/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
				{
					cout << "1" << endl;
				}*/
				it++;
			}
		}
		else
		{
			int popnowe = nower;
			nower = n;
			przedzial tempo;
			tempo.l = nowel;
			tempo.r = -1;
			auto it = --upper_bound(drugi.begin(), drugi.end(), tempo);
			/*if (it != drugi.begin())
			{
				it--;
			}*/
			if(debug)
			{
				cout << "wyw  " << nowel << " " << nower << " " << x.ile << endl;
			}
			while (it != drugi.end() && nowel <= nower)
			{
				int nowel2 = max(nowel, it->l);
				int nower2 = min(nower, it->r);
				if(debug)
				{
					cout << "cur " << nowel << " " << nower << endl;
					cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
				}
				nowel = nower2 + 1;
				if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
				{
					wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
				}
				/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
				{
					//cout << x.l << " " << x.r << " " << x.ile << endl;
					//cout << it->l << " " << it->r << endl;
					//cout << nowel2 << " " << nower2 << endl;
					//cout << nowel << " " << nower << endl;
					//cout << "2" << endl;
				}*/
				it++;
			}
			nowel = 0;
			nower = popnowe;
			tempo.l = nowel;
			tempo.r = -1;
			it = --upper_bound(drugi.begin(), drugi.end(), tempo);
			/*if (it != drugi.begin())
			{
				it--;
			}*/
			if(debug)
			{
				cout << "wyw  " << nowel << " " << nower << " " << x.ile << endl;
			}
			while (it != drugi.end() && nowel <= nower)
			{
				if(debug)
				{
					cout << "cur " << nowel << " " << nower << endl;
					cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
				}
				/*if(pierwszy[0].l == 0 && pierwszy[0].r == 4 && nower == 4)
				{
					cout << it->l << " " << it->r << " " << it->ile << endl;
				}*/
				int nowel2 = max(nowel, it->l);
				int nower2 = min(nower, it->r);
				nowel = nower2 + 1;
				if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
				{
					wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
				}
				/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
				{
					cout << "3" << endl;
				}*/
				it++;
			}
		}
	}
	sort(wynik.begin(), wynik.end());
	if(debug2)
	{
		for(auto x : pierwszy)
		{
			cout << x.l << " " << x.r << " " << x.ile << endl;
		}
		cout << endl;
		for(auto x : drugi)
		{
			cout << x.l << " " << x.r << " " << x.ile << endl;
		}
		cout << endl;
		for(auto x : wynik)
		{
			cout << x.l << " " << x.r << " " << x.ile << endl;
		}
		cout << endl;
	}
	return wynik;
}

void licz(int cur)
{
	if (cur >= 131072)
	{
		return;
	}
	licz(2 * cur);
	licz(2 * cur + 1);
	drz[cur] = lacz_przedzialy(drz[2 * cur], drz[2 * cur + 1]);
}

vector<pair<int, int>> gdzie_kon;

void przedzial(int l, int r, int curl, int curr, int gdzie)
{
	if (curl > r || curr < l)
	{
		return;
	}
	if (l <= curl && r >= curr)
	{
		gdzie_kon.push_back({ curl, gdzie });
	}
	else
	{
		przedzial(l, r, curl, (curl + curr) / 2, gdzie * 2);
		przedzial(l, r, (curl + curr) / 2 + 1, curr, gdzie * 2 + 1);
	}
}

int policz(int stan, int l, int r)
{
	gdzie_kon.clear();
	przedzial(l, r, 1, 131072, 1);
	sort(gdzie_kon.begin(), gdzie_kon.end());
	for (auto x : gdzie_kon)
	{
		//cout << x.second << endl;
		/*for(auto y : drz[x.second])
		{
			//cout << y.l << " " << y.r << " " << y.ile << endl;
		}*/
		//cout << endl;
		int lbin = 0, rbin = drz[x.second].size() - 1, gdzie;
		while (lbin <= rbin)
		{
			int sr = lbin + (rbin - lbin) / 2;
			if (stan < drz[x.second][sr].l)
			{
				rbin = sr - 1;
			}
			else if (stan > drz[x.second][sr].r)
			{
				lbin = sr + 1;
			}
			else
			{
				lbin = rbin + 7;
				gdzie = sr;
			}
		}
		stan += drz[x.second][gdzie].ile;
		stan %= (n + 1);
	}
	return stan;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int m, q, l, r, pref = 0;
	string s;
	cin >> n >> m >> s;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'R')
		{
			pref++;
		}
		else
		{
			i = n + 4;
		}
	}
	for (int i = 0; i < m; i++)
	{
		cin >> gdzie[i];
	}
	for (int i = 0; i < m; i++)
	{
		if (gdzie[i] != 0)
		{
			drz[i + 131072].push_back({ 0, gdzie[i] - 1, gdzie[i] + 1 });
		}
		drz[i + 131072].push_back({ gdzie[i], n, gdzie[i] });
	}
	licz(1);
	/*for(auto x : drz[65539])
	{
		cout << x.l << " " << x.r << " " << x.ile << endl;
	}*/
	cin >> q;
	while (q--)
	{
		int stan;
		cin >> l >> r;
		stan = policz(pref, l, r);
		cout << stan << endl;
	}
	return 0;
}

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