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.