제출 #886670

#제출 시각아이디문제언어결과실행 시간메모리
886670fanwenFinancial Report (JOI21_financial)C++17
5 / 100
263 ms19188 KiB
/* author : bo may can 5 */ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define file(name) \ if(fopen(name".inp", "r")) \ freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); template < class T, T (*f) (T, T), T (*e) ()> struct segment_tree { vector <T> it; int n; void update(int u, T p) { u--; for(it[u += n] += p; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } void set(int u, T p) { u--; for (it[u += n] = p; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } T get(int p) { return it[p += n - 1]; } T get(int l, int r) { l--; T resl = e(), resr = e(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) resl = f(resl, it[l++]); if(r & 1) resr = f(it[--r], resr); } return f(resl, resr); } segment_tree(int n = 0) : n(n), it(n << 1 | 1) { fill(it.begin(), it.end(), T{}); } }; int op(int a, int b) { return a > b ? a : b; } int e() { return 0; } const int MAX = 3e5 + 5; int n, D, dp[MAX]; pair <int, int> a[MAX]; set <int> s, diff; void insert(int u) { s.insert(u); auto it = s.find(u); if(it != s.begin() && next(it) != s.end()) { if(*next(it) - *prev(it) > D) diff.erase(*next(it)); } if(next(it) != s.end()) { int len = *next(it) - u; if(len > D) diff.insert(*next(it)); } if(it != s.begin()) { int len = u - *prev(it); if(len > D) diff.insert(u); } } void you_make_it(void) { cin >> n >> D; for (int i = 1; i <= n; ++i) cin >> a[i].fi, a[i].se = i; sort(a + 1, a + n + 1, [&] (const pair <int, int> &x, const pair <int, int> &y) { return x.fi < y.fi || (x.fi == y.fi && x.se > y.se); }); segment_tree <int, op, e> it(n); int ans = 0, ptr = 1; for (int i = 1; i <= n; ++i) { while(ptr <= n && a[ptr].fi == a[i].fi) { insert(a[ptr++].se); } int d = 0, l = 0; auto iter = diff.lower_bound(a[i].se); if(diff.empty() || iter == diff.begin()) l = 1; else l = *prev(iter); d = it.get(l, a[i].se - 1) + 1; // cout << d << " " << a[i].se << '\n'; ans = max(ans, d); it.set(a[i].se, d); } cout << ans; } signed main() { #ifdef LOCAL freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif file("financial"); auto start_time = chrono::steady_clock::now(); cin.tie(0), cout.tie(0) -> sync_with_stdio(0); you_make_it(); auto end_time = chrono::steady_clock::now(); cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); } // Dream it. Wish it. Do it.

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

Main.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = int; T (* f)(T, T) = op; T (* e)() = e]':
Main.cpp:86:32:   required from here
Main.cpp:17:9: warning: 'segment_tree<int, op, e>::n' will be initialized after [-Wreorder]
   17 |     int n;
      |         ^
Main.cpp:16:16: warning:   'std::vector<int> segment_tree<int, op, e>::it' [-Wreorder]
   16 |     vector <T> it;
      |                ^~
Main.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |     ^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:5: note: in expansion of macro 'file'
  111 |     file("financial");
      |     ^~~~
Main.cpp:12:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:5: note: in expansion of macro 'file'
  111 |     file("financial");
      |     ^~~~
#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...