Submission #423127

#TimeUsernameProblemLanguageResultExecution timeMemory
423127abdzagFinancial Report (JOI21_financial)C++17
31 / 100
221 ms30832 KiB
#include<bits/stdc++.h> #include<unordered_map> #define rep(i,a,b) for(int i=int(a);i<int(b);i++) #define rrep(i,a,b) for(int i=int(a);i>int(b);i--) #define trav(a,v) for(auto& a: v) #define sz(v) v.size() #define all(v) v.begin(),v.end() #define vi vector<int> typedef long long ll; typedef long double ld; typedef unsigned long long ull; const long long inf = 1e15; using namespace std; vector<ll> p(1e6); vector<ll> r(1e6); ll UfindSet(ll cur) { if (p[cur] == cur)return cur; return p[cur] = UfindSet(p[cur]); } void Umerge(ll j, ll i) { ll sj = UfindSet(j); ll si = UfindSet(i); if (sj < si)swap(sj, si); p[sj] = si; return; } struct tree { typedef ll T; static constexpr T unit = -inf; T f(T a, T b) { return max(a, b); } vector<T> s; ll n; tree(ll n=0, T def=unit) : n(n),s(2*n,def){} void update(ll pos, T val) { for (s[pos += n] = val; pos /= 2;) { s[pos] = f(s[pos * 2], s[pos * 2 + 1]); } } T query(ll l, ll r) { T a = unit, b = unit; for (l += n, r += n; l < r; l /= 2, r /= 2) { if (l % 2)a = f(a, s[l++]); if (r % 2)b = f(b, s[--r]); } return f(a, b); } }; int main() { cin.sync_with_stdio(false); int n, d; cin >> n >> d; vector<pair<ll, int>> v(n); rep(i, 0, n) { cin >> v[i].first; v[i].second = -i; } sort(all(v)); vector<ll> dp(n, -inf); rep(i, 0, 1e6)p[i] = i; tree seg(n); rep(i, 0, n) { dp[-v[i].second] = 1; ll cur = d; rrep(j, -v[i].second - 1, max(-1, -v[i].second - d - 1)) { Umerge(-v[i].second, j); if (p[j] != j)break; } ll left = UfindSet(-v[i].second); ll FuckMinAndMax = 1; dp[-v[i].second] = max(FuckMinAndMax, seg.query(left, -v[i].second)+1); seg.update(-v[i].second, dp[-v[i].second]); //rep(a,0,n)cout << p[a] << " "; //cout << endl; //cout << v[i].first << " " << left << " " << seg.query(left, -v[i].second) << endl; //cout << endl; } ll ans = 1; trav(a, dp)ans = max(ans, a); cout << ans << endl; return 0; }

Compilation message (stderr)

Main.cpp: In constructor 'tree::tree(ll, tree::T)':
Main.cpp:35:5: warning: 'tree::n' will be initialized after [-Wreorder]
   35 |  ll n;
      |     ^
Main.cpp:34:12: warning:   'std::vector<long long int> tree::s' [-Wreorder]
   34 |  vector<T> s;
      |            ^
Main.cpp:36:2: warning:   when initialized here [-Wreorder]
   36 |  tree(ll n=0, T def=unit) : n(n),s(2*n,def){}
      |  ^~~~
Main.cpp: In function 'int main()':
Main.cpp:67:6: warning: unused variable 'cur' [-Wunused-variable]
   67 |   ll cur = d;
      |      ^~~
#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...