Submission #1612363
Source Code Expand
//#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 | 2460 Byte |
Status | CE |
Compile Error
./Main.cpp:54:24: fatal error: Union_Find.h: No such file or directory #include "Union_Find.h" ^ compilation terminated.