Submission #1612400
Source Code Expand
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
template <typename T>
class SegmentTree {
using FuncType = std::function<T(const T&, const T&)>;
private:
T* val_p_m;
const T init_val_m;
const int size_m;
const int rank_m;
const FuncType func_m;
T Query_rec(int range_left, int range_right, int node_index, int node_range_left, int node_range_right);
bool Is_valid_index(int index);
public:
SegmentTree(int size, const T& init_val, const FuncType& func);
void Update(int pos, const T& val);
T Query(int range_left, int range_right);
};
template<typename T>
T SegmentTree<T>::Query_rec(int range_left, int range_right, int node_index, int node_range_left, int node_range_right) {
if (node_range_right <= range_left || range_right <= node_range_left) return init_val_m;
if (range_left <= node_range_left && node_range_right <= range_right) return val_p_m[node_index];
int node_range_mid = (node_range_left + node_range_right) / 2;
const T val_left = Query_rec(range_left, range_right, node_index * 2, node_range_left, node_range_mid);
const T val_right = Query_rec(range_left, range_right, node_index * 2 + 1, node_range_mid, node_range_right);
return func_m(val_left, val_right);
}
template<typename T>
inline bool SegmentTree<T>::Is_valid_index(int index) {
return index >= 0 && index < size_m;
}
template<typename T>
SegmentTree<T>::SegmentTree(int size, const T& init_val, const FuncType& func)
: init_val_m(init_val), size_m(size), rank_m((int)std::log2(size) + 1), func_m(func) {
val_p_m = new T[1 << rank_m];
std::fill(val_p_m + (1 << (rank_m - 1)), val_p_m + (1 << rank_m), init_val_m);
for (int i = (1 << (rank_m - 1)) - 1; i >= 1; --i) {
val_p_m[i] = func_m(val_p_m[i * 2], val_p_m[i * 2 + 1]);
}
}
template<typename T>
void SegmentTree<T>::Update(int pos, const T& val) {
assert(Is_valid_index(pos));
int i = pos + (1 << (rank_m - 1));
val_p_m[i] = val;
while (i > 1) {
i /= 2;
val_p_m[i] = func_m(val_p_m[i * 2], val_p_m[i * 2 + 1]);
}
}
template<typename T>
T SegmentTree<T>::Query(int range_left, int range_right) {
assert(Is_valid_index(range_left));
assert(Is_valid_index(range_right - 1));
return Query_rec(range_left, range_right, 1, 0, 1 << (rank_m - 1));
}
template<typename T>
class Max {
public:
const T& operator()(const T& a, const T& b) const {
return std::max<T>(a, b);
}
};
template<typename T>
class Min {
public:
const T& operator()(const T& a, const T& b) const {
return std::min<T>(a, b);
}
};
//#include "IntMod.h"
//typedef IntMod<1000000007> MInt;
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <array>
#include <bitset>
using namespace std;
#define REP(i,a,n) for(int i = (a); i < (int)(n); ++i)
#define REPM(i,n,a) for(int i = ((n) - 1); i >= (a); --i)
#define EPS 0.0001
#define INF 0x3FFFFFFF
#define INFLL 0x3FFFFFFF3FFFFFFF
#define INFD 1.0e+308
#define FLOAT setprecision(16)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(begin(dest), end(dest), val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
// all_of
#if 1
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >; // コスト小を優先
#endif
//#include "Union_Find.h"
int N, M, Q;
int A[100000];
vector<PP> seq;
int idxs[100000];
set<int> Set;
int main() {
cin >> N >> M >> Q;
REP(i, 0, Q) {
cin >> A[i];
--A[i];
}
Fill(idxs, -1);
SegmentTree<int> S(M, INF, Min<int>());
REPM(i, Q, 0) {
int idx = idxs[A[i]];
if (idx == -1) {
seq.push_back(PP(A[i], 1));
idxs[A[i]] = seq.size() - 1;
// S.Update(idxs[A[i]], 1);
} else {
int mn = idx == 0 ? INF : S.Query(0, idx);
if (seq[idx].second != mn && seq[idx].second != N) {
++seq[idx].second;
// S.Update(idx, seq[idx].second);
}
}
}
REP(i, 0, M) {
Set.insert(i);
}
bool ok = true;
// for (PP p : seq) {
// if (p.second == N) {
// Set.erase(p.first);
// } else {
// if (*Set.begin() != p.first) {
// ok = false;
// break;
// }
// Set.erase(p.first);
// }
// }
cout << (ok ? "Yes" : "No") << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - LRU Puzzle |
User |
Aquarius |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5117 Byte |
Status |
WA |
Exec Time |
62 ms |
Memory |
7792 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
1 ms |
640 KB |
0_01.txt |
WA |
1 ms |
640 KB |
0_02.txt |
AC |
1 ms |
640 KB |
0_03.txt |
WA |
1 ms |
640 KB |
1_00.txt |
AC |
1 ms |
640 KB |
1_01.txt |
WA |
1 ms |
640 KB |
1_02.txt |
AC |
37 ms |
6272 KB |
1_03.txt |
AC |
37 ms |
6272 KB |
1_04.txt |
AC |
38 ms |
6272 KB |
1_05.txt |
WA |
37 ms |
6272 KB |
1_06.txt |
AC |
50 ms |
7792 KB |
1_07.txt |
WA |
49 ms |
7792 KB |
1_08.txt |
AC |
50 ms |
7792 KB |
1_09.txt |
AC |
51 ms |
7792 KB |
1_10.txt |
AC |
43 ms |
4468 KB |
1_11.txt |
AC |
43 ms |
4468 KB |
1_12.txt |
WA |
43 ms |
4468 KB |
1_13.txt |
WA |
43 ms |
4468 KB |
1_14.txt |
AC |
42 ms |
4468 KB |
1_15.txt |
AC |
42 ms |
4468 KB |
1_16.txt |
WA |
43 ms |
4468 KB |
1_17.txt |
WA |
42 ms |
4468 KB |
1_18.txt |
AC |
50 ms |
6896 KB |
1_19.txt |
WA |
44 ms |
4724 KB |
1_20.txt |
AC |
49 ms |
6768 KB |
1_21.txt |
WA |
51 ms |
7536 KB |
1_22.txt |
AC |
53 ms |
7408 KB |
1_23.txt |
WA |
54 ms |
5876 KB |
1_24.txt |
AC |
51 ms |
7408 KB |
1_25.txt |
WA |
49 ms |
5620 KB |
1_26.txt |
AC |
31 ms |
1024 KB |
1_27.txt |
WA |
24 ms |
1024 KB |
1_28.txt |
AC |
36 ms |
1152 KB |
1_29.txt |
WA |
36 ms |
1152 KB |
1_30.txt |
AC |
53 ms |
4864 KB |
1_31.txt |
WA |
54 ms |
4992 KB |
1_32.txt |
AC |
47 ms |
3840 KB |
1_33.txt |
WA |
60 ms |
5120 KB |
1_34.txt |
AC |
42 ms |
2936 KB |
1_35.txt |
WA |
46 ms |
4084 KB |
1_36.txt |
AC |
41 ms |
2552 KB |
1_37.txt |
WA |
45 ms |
3828 KB |
1_38.txt |
AC |
49 ms |
6004 KB |
1_39.txt |
WA |
49 ms |
6384 KB |
1_40.txt |
AC |
54 ms |
7028 KB |
1_41.txt |
WA |
53 ms |
7536 KB |
1_42.txt |
AC |
27 ms |
1024 KB |
1_43.txt |
WA |
30 ms |
1024 KB |
1_44.txt |
AC |
31 ms |
1024 KB |
1_45.txt |
WA |
28 ms |
1024 KB |
1_46.txt |
AC |
42 ms |
1920 KB |
1_47.txt |
WA |
45 ms |
2944 KB |
1_48.txt |
AC |
44 ms |
2688 KB |
1_49.txt |
WA |
62 ms |
5504 KB |
1_50.txt |
AC |
34 ms |
1280 KB |
1_51.txt |
WA |
30 ms |
1024 KB |
1_52.txt |
AC |
37 ms |
1664 KB |
1_53.txt |
WA |
37 ms |
1280 KB |
1_54.txt |
AC |
54 ms |
5376 KB |
1_55.txt |
WA |
41 ms |
2944 KB |
1_56.txt |
AC |
59 ms |
6392 KB |
1_57.txt |
WA |
61 ms |
5632 KB |
1_58.txt |
AC |
22 ms |
1024 KB |
1_59.txt |
WA |
25 ms |
1024 KB |
1_60.txt |
AC |
23 ms |
1024 KB |
1_61.txt |
WA |
24 ms |
1024 KB |
1_62.txt |
AC |
38 ms |
2688 KB |
1_63.txt |
WA |
50 ms |
6144 KB |
1_64.txt |
AC |
35 ms |
2432 KB |
1_65.txt |
WA |
57 ms |
5248 KB |
1_66.txt |
AC |
19 ms |
1024 KB |
1_67.txt |
WA |
19 ms |
1024 KB |
1_68.txt |
AC |
19 ms |
1024 KB |
1_69.txt |
WA |
21 ms |
1024 KB |
1_70.txt |
AC |
41 ms |
6016 KB |
1_71.txt |
WA |
51 ms |
4992 KB |