제출 #362755

#제출 시각아이디문제언어결과실행 시간메모리
362755hoaphat1휴가 (IOI14_holiday)C++17
24 / 100
1633 ms65540 KiB
#include<bits/stdc++.h> using namespace std; struct Eins { struct node { long long val = 0; int cnt = 0; int lef = -1, rig = -1; }; vector<node> st; int n; int count = 0; Eins(int n) : n(n) { st.resize(31 * n + 1); } void modify(int&id, int l, int r, int pos, int val) { if (id == -1) id = ++count; if (l == r) { st[id].val += pos * val; st[id].cnt += val; return ; } int mid = l + r >> 1; if (pos <= mid) modify(st[id].lef, l, mid, pos, val); else modify(st[id].rig, mid + 1, r, pos, val); st[id].val = st[id].cnt = 0; if (st[id].lef != -1) { st[id].val += st[st[id].lef].val; st[id].cnt += st[st[id].lef].cnt; } if (st[id].rig != -1) { st[id].val += st[st[id].rig].val; st[id].cnt += st[st[id].rig].cnt; } } long long get(int id, int l, int r, int& num) { if (id == -1) return 0; if (num >= st[id].cnt) { num -= st[id].cnt; return st[id].val; } if (l == r) return 0; int mid = l + r >> 1; return get(st[id].rig, mid + 1, r, num) + get(st[id].lef, l, mid, num); } }; long long findMaxAttraction(int n, int s, int d, int a[]) { long long ans = 0; int L = 0, R = -1; Eins Tree(n); const int maxN = (int) 1e9; int root = 0; auto add = [&](int id) { Tree.modify(root, 0, maxN, a[id], 1); }; auto del = [&](int id) { Tree.modify(root, 0, maxN, a[id], -1); }; auto moveL = [&](int l) { while (L < l) del(L++); while (L > l) add(--L); }; auto moveR = [&](int r) { while (R < r) add(++R); while (R > r) del(R--); }; function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) { if (l > r) return ; int mid = l + r >> 1; int pos = -1; moveR(L); moveL(mid); long long val = -1; for (int i = L; i <= R; i++) { moveR(i); int lim = d - min(s - mid, i - s) - (i - mid); long long now = Tree.get(0, 0, maxN, lim); if (val < now) { val = now; pos = i; } } ans = max(ans, val); assert(pos != -1); solve(l, mid - 1, L, pos); solve(mid + 1, r, pos, R); }; solve(max(0, s - d), s, s, min(n - 1, s + d)); return ans; }

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

holiday.cpp: In member function 'void Eins::modify(int&, int, int, int, int)':
holiday.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In member function 'long long int Eins::get(int, int, int, int&)':
holiday.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In lambda function:
holiday.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = l + r >> 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...