제출 #833145

#제출 시각아이디문제언어결과실행 시간메모리
833145maomao90Financial Report (JOI21_financial)C++17
5 / 100
4065 ms28096 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 300005; int n, d; int a[MAXN]; vii dct; int ans; #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1 int ptr; ii mn[MAXN * 4]; int lz[MAXN * 4], onc[MAXN * 4]; void propo(int u, int lo, int hi) { if (lz[u] == -1) { return; } MLR; mn[lc] = {lz[u], lo}; mn[rc] = {lz[u], mid + 1}; lz[lc] = lz[u]; lz[rc] = lz[u]; lz[u] = -1; } void updt(int s, int e, int x, int u = 1, int lo = 0, int hi = ptr) { if (lo >= s && hi <= e) { if (onc[u] == 0) { x = INF; } mn[u] = {x, lo}; lz[u] = x; return; } propo(u, lo, hi); MLR; if (s <= mid) { updt(s, e, x, lc, lo, mid); } if (e > mid) { updt(s, e, x, rc, mid + 1, hi); } mn[u] = min(mn[lc], mn[rc]); } void togglet(int p, int x, int u = 1, int lo = 0, int hi = ptr) { if (lo == hi) { mn[u] = {x, lo}; onc[u] = x != INF; return; } propo(u, lo, hi); MLR; if (p <= mid) { togglet(p, x, lc, lo, mid); } else { togglet(p, x, rc, mid + 1, hi); } mn[u] = min(mn[lc], mn[rc]); onc[u] = onc[lc] + onc[rc]; } int mx[MAXN * 4]; void updv(int p, int x, int u = 1, int lo = 0, int hi = ptr) { if (lo == hi) { mx[u] = x; return; } MLR; if (p <= mid) { updv(p, x, lc, lo, mid); } else { updv(p, x, rc, mid + 1, hi); } mx[u] = max(mx[lc], mx[rc]); } int qmx(int s, int e, int u = 1, int lo = 0, int hi = ptr) { if (lo >= s && hi <= e) { return mx[u]; } int res = 0; MLR; if (s <= mid) { mxto(res, qmx(s, e, lc, lo, mid)); } if (e > mid) { mxto(res, qmx(s, e, rc, mid + 1, hi)); } return res; } int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> d; REP (i, 1, n + 1) { cin >> a[i]; dct.pb({a[i], i}); } sort(ALL(dct)); int prv = -1; ptr = 0; for (auto [x, i] : dct) { if (x != prv) { ptr++; prv = x; } a[i] = ptr; } memset(lz, -1, sizeof lz); REP (i, 1, n + 1) { cerr << i << ' ' << a[i] << '\n'; updt(a[i], ptr, i); while (i - mn[1].FI > d) { int id = mn[1].SE; updv(id, 0); togglet(id, INF); } int v = qmx(0, a[i] - 1) + 1; int pv = qmx(a[i], a[i]); cerr << ' ' << pv << ' ' << v << '\n'; updv(a[i], max(pv, v)); togglet(a[i], i); } cout << mx[1] << '\n'; return 0; }

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

Main.cpp: In function 'void propo(int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:53:5: note: in expansion of macro 'MLR'
   53 |     MLR;
      |     ^~~
Main.cpp: In function 'void updt(int, int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:70:5: note: in expansion of macro 'MLR'
   70 |     MLR;
      |     ^~~
Main.cpp: In function 'void togglet(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:86:5: note: in expansion of macro 'MLR'
   86 |     MLR;
      |     ^~~
Main.cpp: In function 'void updv(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:101:5: note: in expansion of macro 'MLR'
  101 |     MLR;
      |     ^~~
Main.cpp: In function 'int qmx(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
Main.cpp:114:5: note: in expansion of macro 'MLR'
  114 |     MLR;
      |     ^~~
#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...