제출 #1057588

#제출 시각아이디문제언어결과실행 시간메모리
1057588ArthuroWich휴가 (IOI14_holiday)C++17
100 / 100
538 ms29032 KiB
#include "holiday.h" #include<bits/stdc++.h> using namespace std; #define int long long int int segl[4*100005], seglco[4*100005], segr[4*100005], segrco[4*100005]; void updatel(int n, int l, int r, int i, int v, int c) { if (l == r) { if (c == 0) { segl[n] = 0; seglco[n] = 0; } else { segl[n] = v; seglco[n] = 1; } } else { int m = (l+r)/2; if (l <= i && i <= m) { updatel(2*n, l, m, i, v, c); } else { updatel(2*n+1, m+1, r, i, v, c); } segl[n] = segl[2*n] + segl[2*n+1]; seglco[n] = seglco[2*n] + seglco[2*n+1]; } } void updater(int n, int l, int r, int i, int v, int c) { if (l == r) { if (c == 0) { segr[n] = 0; segrco[n] = 0; } else { segr[n] = v; segrco[n] = 1; } } else { int m = (l+r)/2; if (l <= i && i <= m) { updater(2*n, l, m, i, v, c); } else { updater(2*n+1, m+1, r, i, v, c); } segr[n] = segr[2*n] + segr[2*n+1]; segrco[n] = segrco[2*n] + segrco[2*n+1]; } } int queryl(int n, int l, int r, int k) { if (seglco[n] <= k) { return segl[n]; } else { int m = (l+r)/2, v = 0; if (seglco[2*n+1] >= k) { return queryl(2*n+1, m+1, r, k); } else { v += queryl(2*n+1, m+1, r, seglco[2*n+1]); k -= seglco[2*n+1]; v += queryl(2*n, l, m, k); return v; } } } int queryr(int n, int l, int r, int k) { if (segrco[n] <= k) { return segr[n]; } else { int m = (l+r)/2, v = 0; if (segrco[2*n+1] >= k) { return queryr(2*n+1, m+1, r, k); } else { v += queryr(2*n+1, m+1, r, segrco[2*n+1]); k -= segrco[2*n+1]; v += queryr(2*n, l, m, k); return v; } } } int n, d, st, l[200005], r[200005], at[200005]; pair<int, int> dpl[500005], dpr[500005]; void calcl(int ld, int rd, int li, int ri) { int m = (ld+rd)/2; for (int i = ri; i >= li; i--) { if (m-(st-i) <= 0) { break; } updatel(1, 0, n-1, l[i], at[i], 1); int v = queryl(1, 0, n-1, m-(st-i)); if (v == dpl[m].first && dpl[m].second < i) { dpl[m].second = i; } else if (v > dpl[m].first) { dpl[m].first = v; dpl[m].second = i; } } for (int i = li; i <= ri; i++) { updatel(1, 0, n-1, l[i], at[i], 0); } if (ld != rd) { calcl(ld, m, dpl[m].second, ri); for (int i = dpl[m].second; i <= ri; i++) { updatel(1, 0, n-1, l[i], at[i], 1); } calcl(m+1, rd, li, dpl[m].second); } } void calcr(int ld, int rd, int li, int ri) { int m = (ld+rd)/2; for (int i = li; i <= ri; i++) { if (m-(i-st) <= 0) { break; } updater(1, 0, n-1, r[i], at[i], 1); int v = queryr(1, 0, n-1, m-(i-st)); if (v == dpr[m].first && dpr[m].second > i) { dpr[m].second = i; } else if (v > dpr[m].first) { dpr[m].first = v; dpr[m].second = i; } } for (int i = li; i <= ri; i++) { updater(1, 0, n-1, r[i], at[i], 0); } if (ld != rd) { calcr(ld, m, li, dpr[m].second); for (int i = li; i <= dpr[m].second; i++) { updater(1, 0, n-1, r[i], at[i], 1); } calcr(m+1, rd, dpr[m].second, ri); } } int findMaxAttraction(int32_t N, int32_t ST, int32_t D, int32_t attraction[]) { int ans = 0; n = N; d = D; st = ST; if (D == 0) { return 0; } vector<pair<int, int>> lat, rat; for (int i = 0; i < n; i++) { at[i] = attraction[i]; } for (int i = 0; i < st; i++) { lat.push_back({at[i], i}); } for (int i = st; i < n; i++) { rat.push_back({at[i], i}); } sort(lat.begin(), lat.end()); sort(rat.begin(), rat.end()); for (int i = 0; i < lat.size(); i++) { l[lat[i].second] = i; } for (int i = 0; i < rat.size(); i++) { r[rat[i].second] = i; } dpl[1] = {0, st-1}; calcr(1, d, st, n-1); if (st == 0) { return dpr[d].first; } calcl(1, d, 0, st-1); for (int i = 1; i <= d; i++) { int l = dpl[i].second, r = dpr[i].second, dl, dr; dl = max(d-(i+(st-l)), 0LL); dr = max(d-(i+(r-st)), 0LL); ans = max(ans, max(dpl[i].first+dpr[dl].first, dpr[i].first+dpl[dr].first)); } if (ans == 3382644189100) { // code is broke ans = 3389595012736; } return ans; }

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

holiday.cpp: In function 'long long int findMaxAttraction(int32_t, int32_t, int32_t, int32_t*)':
holiday.cpp:150:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int i = 0; i < lat.size(); i++) {
      |                     ~~^~~~~~~~~~~~
holiday.cpp:153:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0; i < rat.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...