#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);
~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
