제출 #641944

#제출 시각아이디문제언어결과실행 시간메모리
641944Markomafko972Measures (CEOI22_measures)C++14
59 / 100
419 ms42772 KiB
#include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); int n, m, d; int a[250005]; int pos[250005]; vector< pair<int, int> > v; pair<ll, ll> t[2*OFF+5]; ll p[2*OFF+5]; void prop(int x) { if (p[x] == 0 || x >= OFF) return; t[x*2].X += p[x]; t[x*2+1].X += p[x]; t[x*2].Y += p[x]; t[x*2+1].Y += p[x]; p[x*2] += p[x]; p[x*2+1] += p[x]; p[x] = 0; return; } ll query(int a, int b, int l, int r, int x) { if (r <= a || b <= l) { if (a == 0) return -INF; return INF; } if (a <= l && r <= b) { if (a == 0) return t[x].Y; return t[x].X; } prop(x); ll o1 = query(a, b, l, (l+r)/2, x*2); ll o2 = query(a, b, (l+r)/2, r, x*2+1); //cout << o1 << " " << o2 << endl; if (a == 0) return max(o1, o2); return min(o1, o2); } void update(int a, int b, int l, int r, int x, ll kol) { if (r <= a || b <= l) return; if (a <= l && r <= b) { if (kol == INF+1) { t[x].X += -INF; t[x].Y += INF; return; } t[x].X += kol; t[x].Y += kol; p[x] += kol; return; } prop(x); update(a, b, l, (l+r)/2, x*2, kol); update(a, b, (l+r)/2, r, x*2+1, kol); t[x].X = min(t[x*2].X, t[x*2+1].X); t[x].Y = max(t[x*2].Y, t[x*2+1].Y); } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> d; for (int i = 0; i < n; i++) { cin >> a[i]; v.push_back({a[i], i}); } for (int i = n; i < n+m; i++) { cin >> a[i]; v.push_back({a[i], i}); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { pos[v[i].Y] = i; } for (int i = 2*OFF-1; i > 0; i--) { t[i].X = INF; t[i].Y = -INF; } ll sol = 0; int najl = 1e9, najr = -1e9; for (int i = 0; i < n+m; i++) { update(pos[i], pos[i]+1, 0, OFF, 1, INF+1); update(pos[i], pos[i]+1, 0, OFF, 1, a[i]); update(pos[i]+1, n+m, 0, OFF, 1, -d); ll lo = query(0, pos[i]+1, 0, OFF, 1); ll hi = query(pos[i], n+m, 0, OFF, 1); //cout << i << ": " << lo << " " << hi << " " << pos[i] << " " << query(pos[i], pos[i]+1, 0, OFF, 1) << endl; if (najl == 1e9 && najr == -1e9) { najl = pos[i]; najr = pos[i]; } else if (pos[i] >= najl || pos[i] <= najr) sol = max(sol, -hi+lo); else if (pos[i] > najr) { sol = max(sol, (ll)pos[i]*(ll)d-a[i]+lo); najr = pos[i]; } else if (pos[i] < najl) { sol = max(sol, -hi+a[i]-(ll)pos[i]*(ll)d); najl = pos[i]; } if (i >= n) { cout << sol/2; if (sol % 2 == 1) cout << ".5"; cout << " "; } } return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0; i < v.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...