Submission #1249194

#TimeUsernameProblemLanguageResultExecution timeMemory
12491941ncogn1toSails (IOI07_sails)C++20
0 / 100
1096 ms7236 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = LLONG_MAX; // Segment tree to support: find position with minimal value, and increment at position struct SegTree { int n; vector<pair<ll,int>> st; // {value, index} SegTree(int _n): n(_n) { st.assign(4*n, {0, 0}); build(1, 1, n); } void build(int p, int l, int r) { if (l == r) { st[p] = {0, l}; return; } int m = (l + r) >> 1; build(p<<1, l, m); build(p<<1|1, m+1, r); st[p] = min(st[p<<1], st[p<<1|1]); } // increment value at position idx by 1 void update(int p, int l, int r, int idx) { if (l == r) { st[p].first += 1; return; } int m = (l + r) >> 1; if (idx <= m) update(p<<1, l, m, idx); else update(p<<1|1, m+1, r, idx); st[p] = min(st[p<<1], st[p<<1|1]); } // get global minimum {value, index} pair<ll,int> query_min() const { return st[1]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; vector<pair<int,int>> masts(N); int maxH = 0; for(int i = 0; i < N; i++){ cin >> masts[i].first >> masts[i].second; // H, K maxH = max(maxH, masts[i].first); } sort(masts.begin(), masts.end()); SegTree seg(maxH); ll totalIneff = 0; // Process each mast for(auto &p : masts) { int H = p.first; int K = p.second; for(int i = 0; i < K; i++) { auto [cnt, lvl] = seg.query_min(); // but ensure lvl <= H // If lvl > H, search manually among [1..H] if (lvl > H) { // perform a custom query on [1..H] // naive approach: scan tree - but H is large, so we do segment tree recursive // implement helper to query minimal in [1..H] // (Define inline below) function<pair<ll,int>(int,int,int,int,int)> qrange = [&](int p, int l, int r, int i, int j)->pair<ll,int> { if (r < i || l > j) return {INF, -1}; if (l >= i && r <= j) return seg.st[p]; int m = (l + r) >> 1; auto left = qrange(p<<1, l, m, i, j); auto right = qrange(p<<1|1, m+1, r, i, j); return min(left, right); }; auto qr = qrange(1, 1, maxH, 1, H); cnt = qr.first; lvl = qr.second; } totalIneff += cnt; seg.update(1, 1, maxH, lvl); } } cout << totalIneff << "\n"; 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...