QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617461#6836. A Plus B ProblemkaritoRE 0ms0kbC++142.8kb2024-10-06 15:40:122024-10-06 15:40:13

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 15:40:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-06 15:40:12]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS true
#include <iostream>
#include <set>
using namespace std;

struct nod {
	int l, r;
	mutable int x;
	bool operator<(const nod& t)const { if (l == t.l) return r > t.r; return l < t.l; }
};

set<nod> st;

void merge(const set<nod>::iterator& it)
{
	auto il = it, ir = it;
	while (il != st.begin() && il->x == it->x)
		--il;
	if (il->x != it->x)
		++il;
	int r = it->r;
	while (ir != st.end() && ir->x == it->x)
	{
		r = ir->r;
		++ir;
	}
	auto x = nod{ il->l,r,it->x };
	st.erase(il, ir);
	st.insert(x);
	return;
}

auto split(int p)
{
	auto it = --st.upper_bound(nod{ p,-1,0 });
	if (it->l == p)
		return it;
	st.insert(nod{ it->l, p, it->x });
	auto ans = st.insert(nod{ p,it->r,it->x }).first;
	st.erase(it);
	return ans;
}

const int MAXN = 1000010;
int a[MAXN], b[MAXN], h[MAXN];


int main()
{
	ios::sync_with_stdio(false);
	//freopen("t.in", "r", stdin);
	//freopen("t.out", "w", stdout);
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%1d",a + i);
	for (int i = 0; i < n; i++)
		scanf("%1d", b + i);
	int reg = 0,befp=n-1;
	for (int i = n - 1; i >= 0; i--)
	{
		h[i] = a[i] + b[i] + reg;
		reg = h[i]/10, h[i] %= 10;
		if (h[i] != h[befp])
		{
			st.insert(nod{ i + 1,befp + 1,h[befp] });
			befp = i;
		}
	}
	st.insert(nod{ 0,befp + 1,h[befp] });
	for (int i = 0; i < m; i++)
	{
		int r, c, d;
		cin >> r >> c >> d;
		--c;
		int befd = a[c] + b[c];
		if (r == 1)
			a[c] = d;
		else
			b[c] = d;
		int nxtd = a[c] + b[c];
		if (befd % 10 != (--st.upper_bound(nod{ c,-1,0 }))->x)
		{
			++befd, ++nxtd;
		}
		if (befd == nxtd)
		{
			cout << nxtd%10 << " 0\n";
			continue;
		}
		if(c<n-1)
			split(c + 1);
		auto it = split(c);
		it->x = nxtd % 10;
		if (befd / 10 == nxtd / 10 || c == 0)
		{
			cout << it->x << " 2\n";
			merge(it);
			continue;
		}
		else
		{
			int ans = 2;
			if (befd / 10 == 1)
			{
				auto tmp = it; --tmp;
				while (tmp != st.begin() && tmp->x == 0)
				{
					tmp->x = 9;
					ans += tmp->r - tmp->l;
					--tmp;
				}
				if (tmp == st.begin() && tmp->x == 0)
				{
					tmp->x = 9;
					ans += tmp->r - tmp->l;
				}
				else
				{
					auto it = split(tmp->r - 1);
					--it->x;
					ans++;
				}
				merge(it);
				merge(--st.upper_bound(nod{ c - 1, -1, 0 }));
			}
			else
			{
				auto tmp = it; --tmp;
				while (tmp != st.begin() && tmp->x == 9)
				{
					tmp->x = 0;
					ans += tmp->r - tmp->l;
					--tmp;
				}
				if (tmp == st.begin() && tmp->x == 9)
				{
					tmp->x = 0;
					ans += tmp->r - tmp->l;
				}
				else
				{
					auto it = split(tmp->r - 1);
					++it->x;
					ans++;
				}
				merge(it);
				merge(--st.upper_bound(nod{ c - 1, -1, 0 }));
			}
			cout << nxtd % 10 << ' ' << ans << '\n';
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5 5
01234
56789
2 1 0
2 2 1
2 3 2
2 4 3
2 5 4

output:


result: