제출 #951806

#제출 시각아이디문제언어결과실행 시간메모리
951806Vladth11Measures (CEOI22_measures)C++14
100 / 100
227 ms56512 KiB
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #define int long long using namespace std; typedef long long ll; typedef pair <int, int> pii; const ll NMAX = 400001; const int INF = (1LL << 56); const ll nrbits = 20; const ll MOD = 998244353; const int VMAX = 10; int d, cnt; int lazy[NMAX * 4]; vector <pii> tot; struct elem{ int val, nrm; }a[NMAX], b[NMAX]; bool cmp(pii aa, pii bb){ int prim = a[aa.first].val; if(aa.second == 1) prim = b[aa.first].val; int sec = a[bb.first].val; if(bb.second == 1) sec = b[bb.first].val; return prim < sec; } struct Node { int maxim, minim; int sol; } aint[NMAX * 4]; void propaga(int node, int st, int dr) { if(st != dr) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } aint[node].maxim += lazy[node]; aint[node].minim += lazy[node]; lazy[node] = 0; } Node combine(Node a, Node b) { Node sol = {-INF, INF, 0}; sol.sol = max(a.sol, b.sol); sol.sol = max(sol.sol, a.maxim - b.minim); sol.maxim = max(a.maxim, b.maxim); sol.minim = min(a.minim, b.minim); return sol; } void activate(int node, int st, int dr, int x, int val) { propaga(node, st, dr); if(st == dr) { aint[node].maxim += INF + val; aint[node].minim -= INF; aint[node].minim += val; aint[node].sol = 0; return; } int mid = (st + dr) / 2; if(x <= mid) activate(node * 2, st, mid, x, val); else activate(node * 2 + 1, mid + 1, dr, x, val); propaga(node * 2, st, mid); propaga(node * 2 + 1, mid + 1, dr); aint[node] = combine(aint[node * 2], aint[node * 2 + 1]); } void update(int node, int st, int dr, int a, int b, int val) { if(a > dr) return; propaga(node, st, dr); if(a <= st && dr <= b) { lazy[node] += val; return; } int mid = (st + dr) / 2; if(a <= mid) update(node * 2, st, mid, a, b, val); if(b > mid) update(node * 2 + 1, mid + 1, dr, a, b, val); propaga(node * 2, st, mid); propaga(node * 2 + 1, mid + 1, dr); aint[node] = combine(aint[node * 2], aint[node * 2 + 1]); } signed main() { #ifdef HOME ifstream cin(".in"); ofstream cout(".out"); #endif // HOME ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); for(int i = 0; i < NMAX * 4; i++) { aint[i].maxim = -INF; aint[i].minim = INF; aint[i].sol = 0; } int n, i, m, x; cin >> n >> m >> d; tot.clear(); for(i = 1; i <= n; i++) { cin >> a[i].val; tot.push_back({i, 0}); } for(i = 1; i <= m; i++) { cin >> b[i].val; tot.push_back({i, 1}); } sort(tot.begin(), tot.end(), cmp); for(int i = 0; i < tot.size(); i++){ if(tot[i].second == 1){ b[tot[i].first].nrm = i + 1; }else{ a[tot[i].first].nrm = i + 1; } } cnt = tot.size(); for(i = 1; i <= n; i++) { update(1, 1, cnt, a[i].nrm + 1, cnt, -d); activate(1, 1, cnt, a[i].nrm, a[i].val); } for(i = 1; i <= m; i++) { update(1, 1, cnt, b[i].nrm + 1, cnt, -d); activate(1, 1, cnt, b[i].nrm, b[i].val); propaga(1, 1, cnt); int sol = max(0LL, aint[1].sol); cout << sol/2; if(sol%2) cout << ".5"; cout << " "; } return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:122:22: 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]
  122 |     for(int i = 0; i < tot.size(); i++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:110:18: warning: unused variable 'x' [-Wunused-variable]
  110 |     int n, i, m, x;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...