Submission #1555034
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int maxn = 200100;
int n, m;
int a[maxn + 5];
int col[maxn + 5];
set<pair<int, int> > all;
int ri[maxn + 5];
int pre[maxn + 5];
int fa[maxn + 5];
int main()
{
#ifdef matthew99
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
REP(i, 0, n) scanf("%d", a + i), --a[i];
all.insert(mp(-1, 0));
m = 0;
REP(i, 0, n)
{
auto u = --all.lower_bound(mp(a[i], 0));
pair<int, int> to_add = mp(a[i], u->y);
int nxt = -1;
if (!~u->x) nxt = u->y + 1, ++m;
ri[u->y] = a[i];
pre[a[i]] = u->x;
col[a[i]] = u->y;
all.erase(u);
all.insert(to_add);
if (~nxt) all.insert(mp(-1, nxt));
}
queue<int> q;
REP(i, 0, m) q.push(i);
int ans = 0;
int lst = n - 1;
vector<int> seq;
for (int i = n - 2; i >= 0; --i)
{
if (col[i] != col[i + 1] && (col[i] - col[i + 1] + m) % m + (col[i + 1] - col[lst] + m) % m <= m)
{
++ans;
lst = i + 1;
}
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Strange Sorting |
User |
matthew99 |
Language |
C++14 (GCC 5.4.1) |
Score |
2400 |
Code Size |
1571 Byte |
Status |
AC |
Exec Time |
132 ms |
Memory |
13568 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:42:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, 0, n) scanf("%d", a + i), --a[i];
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
2400 / 2400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
58 ms |
2688 KB |
in10.txt |
AC |
58 ms |
2688 KB |
in11.txt |
AC |
58 ms |
2688 KB |
in12.txt |
AC |
58 ms |
2688 KB |
in13.txt |
AC |
58 ms |
2688 KB |
in14.txt |
AC |
58 ms |
2688 KB |
in15.txt |
AC |
58 ms |
2688 KB |
in16.txt |
AC |
58 ms |
2688 KB |
in17.txt |
AC |
59 ms |
2688 KB |
in18.txt |
AC |
58 ms |
2688 KB |
in19.txt |
AC |
58 ms |
2688 KB |
in2.txt |
AC |
58 ms |
2688 KB |
in20.txt |
AC |
58 ms |
2688 KB |
in21.txt |
AC |
31 ms |
2560 KB |
in22.txt |
AC |
132 ms |
13568 KB |
in23.txt |
AC |
1 ms |
256 KB |
in3.txt |
AC |
58 ms |
2688 KB |
in4.txt |
AC |
58 ms |
2688 KB |
in5.txt |
AC |
58 ms |
2688 KB |
in6.txt |
AC |
58 ms |
2688 KB |
in7.txt |
AC |
59 ms |
2688 KB |
in8.txt |
AC |
58 ms |
2688 KB |
in9.txt |
AC |
58 ms |
2688 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |