QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673441#2387. Min Max ConvertYarema#WA 425ms8380kbC++234.5kb2024-10-24 22:23:492024-10-24 22:23:50

Judging History

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

  • [2024-10-24 22:23:50]
  • 评测
  • 测评结果:WA
  • 用时:425ms
  • 内存:8380kb
  • [2024-10-24 22:23:49]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int INF = 1e9 + 47;

struct Segtree
{
	struct Node
	{
		int mn = INF, mx = 0, st = -1;
	};
	int n;
	vector<Node> t;
	
	Segtree() {}
	Segtree(int _n)
	{
		n = 1;
		while (n < _n) n *= 2;
		t.resize(2 * n - 1);
	}
	
	void push(int v, int tl, int tr)
	{
		if (t[v].st == -1)
			return;
		t[v].mn = min(t[v].mn, t[v].st);
		t[v].mx = max(t[v].mx, t[v].st);
		if (tl + 1 != tr)
		{
			t[v * 2 + 1].st = t[v].st;
			t[v * 2 + 2].st = t[v].st;
		}
		t[v].st = -1;
	}
	void upd(int v, int tl, int tr, int l, int r, int x)
	{
		push(v, tl, tr);
		if (l <= tl && tr <= r)
		{
			t[v].st = x;
			push(v, tl, tr);
			return;
		}
		if (l >= tr || tl >= r)
			return;
		int tm = (tl + tr) / 2;
		upd(2 * v + 1, tl, tm, l, r, x);
		upd(2 * v + 2, tm, tr, l, r, x);
		t[v].mn = min(t[v * 2 + 1].mn, t[v * 2 + 2].mn);
		t[v].mx = max(t[v * 2 + 1].mx, t[v * 2 + 2].mx);
	}
	void upd(int l, int r, int x)
	{
		upd(0, 0, n, l, r, x);
	}
	PII query(int v, int tl, int tr, int l, int r)
	{
		push(v, tl, tr);
		//cerr << v << ' ' << tl << ' ' << tr << ' ' << t[v].mn << ' ' << t[v].mx << '\n';
		if (l <= tl && tr <= r)
			return {t[v].mn, t[v].mx};
		if (l >= tr || tl >= r)
			return {INF, -INF};
		int tm = (tl + tr) / 2;
		PII p1 = query(2 * v + 1, tl, tm, l, r);
		PII p2 = query(2 * v + 2, tm, tr, l, r);
		return {min(p1.F, p2.F), max(p1.S, p2.S)};
	}
	PII query(int l, int r)
	{
		PII res = query(0, 0, n, l, r);
		//cerr << "Query " << l << ' ' << r << ' ' << res.F << ' ' << res.S << '\n';
		return {res.F, res.S};
	}
} st;

const int N = 100'447;
VI g[N];
VI tps;
bool used[N];

void dfs(int v)
{
	used[v] = 1;
	for (auto to : g[v])
		if (!used[to])
			dfs(to);
	tps.PB(v);
}

int GetL(int pos, int L)
{
	PII p = st.query(L, pos + 1);
	if (p.F == p.S)
		return L;
	int l = L, r = pos;
	while (l + 1 < r)
	{
		int m = (l + r) / 2;
		p = st.query(m, pos + 1);
		if (p.F == p.S)
			r = m;
		else
			l = m;
	}
	//cerr << pos << ' ' << L << ' ' << r << '\n';
	return r;
}


int GetR(int pos, int R)
{
	PII p = st.query(pos, R + 1);
	if (p.F == p.S)
		return R;
	int l = pos, r = R;
	while (l + 1 < r)
	{
		int m = (l + r) / 2;
		p = st.query(pos, m + 1);
		if (p.F == p.S)
			l = m;
		else
			r = m;
	}
	return l;
}

string s = "";
VI l, r;
	
void upd(int L, int R, int x, int pl, int pr)
{
	//cerr << "UPD " << L << ' ' << R << ' ' << x << '\n';
	int val = st.query(L, L + 1).F;
	if (val < x)
		s += 'M';
	else
		s += 'm';
	l.PB(L + pl);
	r.PB(R + pr);
	st.upd(L, R + 1, x);
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	int n;
	cin >> n;
	VI a(n), b(n);
	FOR (i, 0, n) cin >> a[i];
	FOR (i, 0, n) cin >> b[i];
	
	vector<PII> v;
	int val = b[0], cnt = 1;
	FOR (i, 1, n)
	{
		if (b[i] == val)
			cnt++;
		else
		{
			v.PB({val, cnt});
			val = b[i];
			cnt = 1;
		}
	}
	v.PB({val, cnt});
	VI c(1, 0);
	FOR (i, 0, SZ(v))
		c.PB(c.back() + v[i].S);
	//cerr << v[0].F << ' ' << v[1].F << ' '<< v[2].F << '\n';
	int j = 0;
	VI pos;
	FOR (i, 0, n)
	{
		if (j < SZ(v) && a[i] == v[j].F)
		{
			pos.PB(i);
			j++;		
		}
	}
	if (j < SZ(v))
	{
		cout << -1 << '\n';
		return 0;
	}
	st = Segtree(n);
	FOR (i, 0, n)
		st.upd(i, i + 1, a[i]);
		
	
	j = 0;
	int idx = 0;
	FOR (i, 0, SZ(pos))
	{
		while (idx + v[j].S <= pos[i]) 
			idx += v[j++].S;
		g[i].PB(j);		
	}
	FOR (i, 0, SZ(pos))
	{
		if (!used[i])
			dfs(i);
	}
	reverse(ALL(tps));
	for (auto i : tps)
	{
		int ps = pos[i];
		int L = c[i];
		int R = c[i + 1] - 1;
		int ptr = GetL(ps, L);
		//cerr << ps << ' ' << L << ' ' << R << ' ' << ptr << '\n';
		while (ptr > L)
		{
			int x = GetL(ptr - 1, L);
			upd(x, ptr - 1, a[ps], 0, 1);
			ptr = x;
		}
		ptr = GetR(ps, R);
		while (ptr < R)
		{
			int x = GetR(ptr + 1, R);
			//cerr << i << ' ' << ptr << ' ' << x << ' ' << R << '\n';
			upd(ptr + 1, x, a[ps], -1, 0);
			ptr = x;			
		}
	}
	assert(SZ(s) <= 2 * n);
	cout << SZ(s) << '\n';
	FOR (i, 0, SZ(s))
	{
		cout << s[i] << ' ' << l[i] + 1 << ' ' << r[i] + 1 << '\n';
	}
	
	
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 425ms
memory: 8380kb

input:

100000
80159 24037 50544 49029 20937 95595 93373 58274 55943 97218 6019 21069 7470 92698 25184 8879 68760 75476 81465 87494 92468 11304 66134 85457 88083 59682 95187 18518 63052 61310 69855 4557 82231 40498 38847 95156 2291 94195 90442 94252 27042 63660 32300 25128 47881 8924 61749 44499 7315 93110 ...

output:

126134
M 77266 77267
M 77265 77266
M 77264 77265
M 77263 77264
M 77262 77263
M 77261 77262
M 77260 77261
M 77259 77260
M 77258 77259
M 77257 77258
M 77256 77257
M 77255 77256
M 77254 77255
M 77253 77254
M 77252 77253
M 77251 77252
M 77250 77251
M 77249 77250
M 77248 77249
M 77247 77248
M 77246 77247...

result:

wrong answer Wrong Answer!