# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
878443 |
2023-11-24T11:24:29 Z |
deadeye0 |
Sails (IOI07_sails) |
C++17 |
|
34 ms |
10340 KB |
#include <bits/stdc++.h>
using namespace std;
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);
}
int 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 time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
18 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
4868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
6336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
34 ms |
9968 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
34 ms |
10212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
34 ms |
10340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |