Submission #878444

#TimeUsernameProblemLanguageResultExecution timeMemory
878444deadeye0Sails (IOI07_sails)C++17
55 / 100
37 ms10440 KiB
#include <bits/stdc++.h> using namespace std; #define int long long using ll = long long; #define fi first #define si second #define ar array #define pb push_back typedef pair<ll,int> pi; typedef tuple<int,int,int> ti; typedef vector<int> vi; template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;} template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;} void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) const int N = 100010; int n; int h[N], k[N]; int ans[N]; ll total, ret; multiset<pi> st; ll fw[N], fw2[N]; void update(int x, int y, ll v) { for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1); for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; } ll sum (int x) { ll res = 0; for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx]; return res; } ll query(int x, int y) { //inclusive return sum(y)-sum(x-1); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin.exceptions(ios::badbit|ios::failbit); cin >> n; int mx = 0; for (int i = 0; i < n; ++i) { cin >> h[i] >> k[i]; total += k[i]; chmax(mx, h[i]); } for (int i = 0; i < n; ++i) update(1, h[i], 1); for (int i = 1; i <= mx; ++i) st.insert({query(i, i), i}); int cur = 0; while (1) { int rows = st.size(); if (total >= rows) { total -= rows; ++cur; } else { int df = rows - total; while (df) { ans[st.begin()->si] = cur; st.erase(st.find(*st.begin())); --df; } for (auto i: st) ans[i.si] = cur + 1; break; } while (st.size() && st.begin()->fi == cur) { ans[st.begin()->si] = cur; st.erase(st.find(*st.begin())); } } for (int i = 1; i <= mx; ++i) { ll val = ans[i] * (ans[i] + 1) / 2 - ans[i]; ret += val; } cout << ret; return 0; }
#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...
#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...