Submission #802087

#TimeUsernameProblemLanguageResultExecution timeMemory
802087rxlfd314Financial Report (JOI21_financial)C++17
5 / 100
405 ms207520 KiB
#include <bits/stdc++.h> using namespace std; using ari2 = array<int, 2>; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, D; cin >> N >> D; vector<int> A(N); for (int &i : A) { cin >> i; } vector<int> cmp = A; sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); struct BIT { vector<deque<ari2>> fen; BIT(int n) {fen.resize(n);} void upd(int i, int j, int v) { for (; i < fen.size(); i += i+1 & -i-1) { for (; fen[i].size() && fen[i].back()[0] <= v; fen[i].pop_back()); fen[i].push_back({v, j}); } } int qry(int i, int j) { int ret = 0; for (; ~i; i -= i+1 & -i-1) { for (; fen[i].size() && fen[i].front()[1] < j; fen[i].pop_front()); ret = max(ret, fen[i].size() ? fen[i].front()[0] : 0); } return ret; } } fen(cmp.size()); int ans = 0; for (int i = 0; i < N; i++) { int j = lower_bound(cmp.begin(), cmp.end(), A[i]) - cmp.begin(); int x = fen.qry(j-1, i-D) + 1; ans = max(ans, x); fen.upd(j, i, x); } cout << ans << '\n'; }

Compilation message (stderr)

Main.cpp: In member function 'void main()::BIT::upd(int, int, int)':
Main.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for (; i < fen.size(); i += i+1 & -i-1) {
      |           ~~^~~~~~~~~~~~
Main.cpp:23:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   23 |    for (; i < fen.size(); i += i+1 & -i-1) {
      |                                ~^~
Main.cpp: In member function 'int main()::BIT::qry(int, int)':
Main.cpp:30:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   30 |    for (; ~i; i -= i+1 & -i-1) {
      |                    ~^~
#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...