Submission #1612369
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]; 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 | 5063 Byte |
Status | CE |
Compile Error
./Main.cpp: In instantiation of ‘SegmentTree<T>::SegmentTree(int, const T&, const FuncType&) [with T = int; SegmentTree<T>::FuncType = std::function<int(const int&, const int&)>]’: ./Main.cpp:160:39: required from here ./Main.cpp:48:6: error: ‘fill’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive] fill(val_p_m + (1 << (rank_m - 1)), val_p_m + (1 << rank_m), init_val_m); ^ In file included from /usr/include/c++/5/deque:66:0, from /usr/include/c++/5/stack:60, from ./Main.cpp:105: /usr/include/c++/5/bits/deque.tcc:949:5: note: ‘template<class _Tp> void std::fill(const std::_Deque_iterator<_Tp, _Tp&, _Tp*>&, const std::_Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&)’ declared here, later in the translation unit fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, ^