제출 #1046349

#제출 시각아이디문제언어결과실행 시간메모리
1046349hiuwsssSails (IOI07_sails)C++14
100 / 100
45 ms2652 KiB
/* Ý tưởng giống bài BOI11_grow trong OJUZ ta k cần quan tâm đến việc nó nằm ở cột nào, mà chỉ cần quan tâm đến các tầng, tầng x có Sx buồm thì của giá trị của nó sẽ Sx * (Sx - 1) /2; Ta có bài toán tham lam sau : sắp xếp các cột theo độ cao tăng dần, để cho tổng nhỏ nhất thì các giá trị càng gần nhau và càng nhỏ càng tốt, từ đó ta có thể tham lam Xét tới cột i, có độ cao h, có c lá buồm thì ta sẽ chọn ra c tầng nhỏ nhất để cho vào. Ta muốn xây dựng 1 cây BIT tăng dàn, vì ở độ cao càng bé thì sẽ càng có nhiều cột thỏa mãn, nên việc tham lam sẽ luôn có cột càng nhỏ nên ta cài đặt như ở dưới. */ #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> i) & 1LL) #define ll long long template<class T> bool minimize(T &x, const T &y) { return x > y ? x = y, 1 : 0; } template<class T> bool maximize(T &x, const T &y) { return x < y ? x = y, 1 : 0; } const int MAX = 1e5 + 5; const int max_log = 18; int n; pair<int, int> a[MAX]; struct FenwickTree { int n; vector<int> bit; FenwickTree(int _n = 0) { n = _n; bit.assign(n + 5, 0); } void update(int u, int delta) { for (; u <= n; u += (u & (-u))) bit[u] += delta; } void update(int l, int r, int delta) { if (l > r) return; update(l, delta); update(r + 1, -delta); } int getValue(int u) { int ans = 0; for (; u > 0; u -= (u & (-u))) ans += bit[u]; return ans; } int getPos(int value) { int pos = 0, sum = 0; FORD(i, max_log, 0) if (pos + MASK(i) <= n && sum + bit[pos + MASK(i)] <= value) { pos |= MASK(i); sum += bit[pos]; } return pos; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "" if (fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n; int maxHeight = 0; FOR(i, 1, n) { cin >> a[i].first >> a[i].second; maximize(maxHeight, a[i].first); } sort(a + 1, a + n + 1); FenwickTree myBit(maxHeight); FOR(i, 1, n) { int h = a[i].first, c = a[i].second; int L = maxHeight - h + 1; int value = myBit.getValue(L + c - 1); int R = myBit.getPos(value); int r = max(L - 1, myBit.getPos(value - 1)); myBit.update(L, r, 1); myBit.update(R - (c - (r - L + 1)) + 1, R, 1); } ll res = 0; FOR(i, 1, maxHeight) { int cur = myBit.getValue(i); res += 1LL * cur * (cur - 1) / 2; } cout << res; return (0 ^ 0); } //hiuwsss

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

sails.cpp: In function 'int main()':
sails.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen(TASK".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen(TASK".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...