Submission #137768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137768	2019-07-28T09:31:08 Z	김현수(#3360)	RLE (BOI06_rle)	C++14	100 / 100	1387 ms	53472 KB

rle

#include<bits/stdc++.h>
#define X first
#define Y second
#define pii MyFuckingPair
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 MyFuckingPair {
	int X, Y;
	bool operator < (const MyFuckingPair &T) const {
		if(X != T.X) return X < T.X;
		return Y < T.Y;
	}
};

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:135: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:100: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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
rle.cpp:110: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	4 ms	1400 KB	Output is correct
3	Correct	4 ms	1400 KB	Output is correct
4	Correct	4 ms	1400 KB	Output is correct
5	Correct	4 ms	1400 KB	Output is correct
6	Correct	25 ms	2464 KB	Output is correct
7	Correct	176 ms	7904 KB	Output is correct
8	Correct	234 ms	10332 KB	Output is correct
9	Correct	416 ms	21200 KB	Output is correct
10	Correct	175 ms	7644 KB	Output is correct
11	Correct	143 ms	7428 KB	Output is correct
12	Correct	348 ms	17500 KB	Output is correct
13	Correct	381 ms	16720 KB	Output is correct
14	Correct	177 ms	8292 KB	Output is correct
15	Correct	92 ms	5096 KB	Output is correct
16	Correct	360 ms	17104 KB	Output is correct
17	Correct	490 ms	21072 KB	Output is correct
18	Correct	508 ms	22516 KB	Output is correct
19	Correct	1281 ms	53472 KB	Output is correct
20	Correct	1387 ms	53296 KB	Output is correct