제출 #436862

#제출 시각아이디문제언어결과실행 시간메모리
436862vulpes2Financial Report (JOI21_financial)C++17
33 / 100
4049 ms42592 KiB
//#include <atcoder/maxflow.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #include <iostream> #include <map> #include <list> #include <set> #include <algorithm> #include <vector> #include <string> #include <functional> #include <queue> #include <deque> #include <stack> #include <unordered_map> #include <unordered_set> #include <cmath> #include <iterator> #include <random> #include <chrono> #include <complex> #include <bitset> #include <fstream> #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i) #define set_map_includes(set, elt) (set.find((elt)) != set.end()) #define readint(i) int i; cin >> i #define readll(i) ll i; cin >> i #define readdouble(i) double i; cin >> i #define readstring(s) string s; cin >> s typedef long long ll; //using namespace __gnu_pbds; //using namespace atcoder; using namespace std; const ll modd = (1000LL * 1000LL * 1000LL + 7LL); //const ll modd = 998244353; template<class T> class SegmentTree2 { public: SegmentTree2(const vector<T>& data, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) { Initialize(data); } SegmentTree2(int n, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) { vector<T> temp(n, zv); Initialize(temp); } T operator[](int i) { return tree[B+i]; } T GetEvaluation(int L, int R) { // "min/max" on interval [L,R); 0-based indexing, as usual if (R<=L) { return zv; } return GetEvaluationHelper(L, R, 0, B, 1); } void SetVal(int i, T val) { tree[B+i] = val; for(int j = (B + i) / 2; j >= 1; j /= 2) { tree[j] = f(tree[2*j], tree[2*j+1]); } } private: vector<T> tree; int B; // power of two greater than size of input data T zv; function<T(T,T)> f; void Initialize(const vector<T>& data) { B = 1; while(B < data.size()) {B *= 2; } tree = std::move(vector<T>(2*B, zv)); copy(data.begin(), data.end(), next(tree.begin(), B)); for(int i = B - 1; i >= 1; --i) { tree[i] = f(tree[2*i], tree[2*i+1]); } } T GetEvaluationHelper(int L, int R, int start, int length, int tree_index) { if (L==R) { return zv; } if ((L==start) && (R==start+length)) { return tree[tree_index]; } int midpoint = start + length/2; T left_ = zv, right_ = zv; if (L<=min(midpoint,R)) { left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index); } if (max(midpoint,L)<=R) { right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1); } return f(left_, right_); } }; class block { public: vector<bool> occupied; int dd; block(int n, int d) : occupied(n, false), dd(d) {} void add(int i) { occupied[i] = true; } int upto(int i) { forr(j,i,occupied.size()) { if (j+dd>occupied.size()) { break; } bool occ = true; forr(k,j,dd) { occ &= occupied[k]; } if (occ) { return j+dd; } } return occupied.size(); } }; int main(int argc, char *argv[]) { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> rand_gen(0, modd); // rand_gen(rng) gets the rand no ios_base::sync_with_stdio(false); cin.tie(0); cout.precision(12); // readint(test_cases); int test_cases = 1; forr(t, 1, test_cases) { readint(n); readint(d); vector<int> ans(n); map<int, vector<int>> vals; forr(i,0,n) { readint(aa); vals[aa].push_back(i); } block bl(n, d); int ret = 0; SegmentTree2<int> seg_tree(n, [](int x, int y){ return max(x,y); }, 0); auto it = vals.end(); while (it!=vals.begin()) { --it; for(int j : it->second) { bl.add(j); int val = 1 + seg_tree.GetEvaluation(j+1, bl.upto(j+1)); seg_tree.SetVal(j, val); ret = max(ret, val); } } cout << ret << endl; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'int block::upto(int)':
Main.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:122:11: note: in expansion of macro 'forr'
  122 |           forr(j,i,occupied.size()) {
      |           ^~~~
Main.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |               if (j+dd>occupied.size()) { break; }
      |                   ~~~~^~~~~~~~~~~~~~~~
Main.cpp: In instantiation of 'void SegmentTree2<T>::Initialize(const std::vector<_Tp>&) [with T = int]':
Main.cpp:56:11:   required from 'SegmentTree2<T>::SegmentTree2(int, std::function<T(T, T)>, T) [with T = int]'
Main.cpp:160:78:   required from here
Main.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |           while(B < data.size()) {B *= 2;  }
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...