Submission #137771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137771	2019-07-28T09:32:02 Z	khsoo01	RLE (BOI06_rle)	C++11	100 / 100	1493 ms	53328 KB

rle

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2000005, L = 131072, inf = 1e9;

int m, n, rn, a[N], sw[N], crm;
ll c[N];

vector<int> ans;

void append (int V, ll C) {
	if(!rn || a[rn] != V) rn++;
	a[rn] = V;
	c[rn] += C;
}

int cost1 (ll L) {return (L+m-1)/m*3;}

void make1 (ll L) {
	while(L) {
		int C = min(m-1ll, L-1);
		ans.push_back(C);
		ans.push_back(crm);
		ans.push_back(crm);
		L -= C+1;
	}
}

int cost2 (ll L) {
	int R = L%(m+2);
	if(R == 0 || R > 2) return (L+m+1)/(m+2)*3;
	else return L/(m+2)*3+R;
}

void make2 (ll L, int I) {
	while(L > 3) {
		int C = min(m-1ll, L-3);
		ans.push_back(C);
		ans.push_back(I);
		ans.push_back(crm);
		L -= C + 3;
	}
	while(L) {
		ans.push_back(I);
		L--;
	}
}

void swit (int I) {
	ans.push_back(0);
	ans.push_back(crm);
	ans.push_back(I);
	crm = I;
}

struct segtree {
	pii v[2*L];
	void init () {
		for(int i=1;i<m;i++) {
			v[i+L] = {3, i};
		}
		for(int i=L;--i;) {
			v[i] = min(v[2*i], v[2*i+1]);
		}
	}
	void upd (int P, int V) {
		P += L; v[P].X += V; P /= 2;
		while(P) {
			v[P] = min(v[2*P], v[2*P+1]);
			P /= 2;
		}
	}
	pii get (int S, int E) {
		S += L; E += L;
		pii R = {inf, inf};
		while(S <= E) {
			if(S%2 == 1) R = min(R, v[S++]);
			if(E%2 == 0) R = min(R, v[E--]);
			S /= 2; E /= 2;
		}
		return R;
	}
} seg;

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++) {
		int T;
		scanf("%d",&T);
		if(T != crm) {
			append(T, 1);
			continue;
		}
		i += 2;
		int A, B;
		scanf("%d%d",&A,&B);
		if(T == A) append(A, B+1);
		else if(B) append(A, B+3);
		else crm = A;
	}
	seg.init();
	for(int i=1;i<=rn;i++) {
		int X = cost1(c[i]) - cost2(c[i]);
		auto V1 = min(seg.get(0, a[i]-1), seg.get(a[i]+1, m-1)), V2 = seg.get(a[i], a[i]);
		if(X > V1.X - V2.X + 3) {
			seg.upd(a[i], V1.X - V2.X + 3);
			sw[i] = V1.Y;
		}
		else {
			seg.upd(a[i], X);
			sw[i] = -1;
		}
	}
	crm = seg.get(0, m-1).Y;
	for(int i=rn;i>=1;i--) {
		if(crm == a[i] && ~sw[i]) swit(sw[i]);
		if(crm == a[i]) make1(c[i]);
		else make2(c[i], a[i]);
	}
	if(crm != 0) swit(0);
	printf("%d\n", ans.size());
	for(int i=ans.size();i--;) {
		printf("%d ", ans[i]);
	}
}

Compilation message

rle.cpp: In function 'int main()':
rle.cpp:126:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
rle.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
  ~~~~~^~~~~~~~~~~~~~
rle.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
rle.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1400 KB	Output is correct
2	Correct	3 ms	1400 KB	Output is correct
3	Correct	3 ms	1400 KB	Output is correct
4	Correct	4 ms	1372 KB	Output is correct
5	Correct	4 ms	1400 KB	Output is correct
6	Correct	25 ms	2436 KB	Output is correct
7	Correct	171 ms	7896 KB	Output is correct
8	Correct	227 ms	10336 KB	Output is correct
9	Correct	439 ms	21180 KB	Output is correct
10	Correct	169 ms	7644 KB	Output is correct
11	Correct	141 ms	7360 KB	Output is correct
12	Correct	352 ms	17640 KB	Output is correct
13	Correct	370 ms	16824 KB	Output is correct
14	Correct	174 ms	8336 KB	Output is correct
15	Correct	93 ms	5100 KB	Output is correct
16	Correct	356 ms	17232 KB	Output is correct
17	Correct	483 ms	21180 KB	Output is correct
18	Correct	509 ms	22352 KB	Output is correct
19	Correct	1376 ms	53260 KB	Output is correct
20	Correct	1493 ms	53328 KB	Output is correct