# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
500677 |
2021-12-31T18:47:15 Z |
600Mihnea |
Sails (IOI07_sails) |
C++17 |
|
376 ms |
5224 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gauss(int x) {
return x * (x + 1) / 2;
}
struct Data {
int total;
int need;
};
bool operator < (Data a, Data b) {
return a.total < b.total;
}
const int N = (int) 1e5 + 7;
const int INF = (int) 1e18;
int n;
Data guys[N];
int lazy[4 * N];
int innerValue[N];
int limit;
void push(int v, int tl, int tr) {
if (lazy[v]) {
if (tl == tr) {
innerValue[tl] += lazy[v];
} else {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
}
void add(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lazy[v]++;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r);
add(2 * v + 1, tm + 1, tr, l, r);
}
int getValue(int v, int tl, int tr, int i) {
push(v, tl, tr);
if (tr < i || i < tl) {
assert(0);
}
if (tl == tr) {
return innerValue[tl];
}
int tm = (tl + tr) / 2;
if (i <= tm) {
return getValue(2 * v, tl, tm, i);
} else {
return getValue(2 * v + 1, tm + 1, tr, i);
}
}
void add(int l, int r) {
if (l > r) {
return;
}
add(1, 1, limit, l, r);
}
int get(int i) {
return getValue(1, 1, limit, i);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
//freopen ("input", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> guys[i].total >> guys[i].need;
}
sort(guys + 1, guys + n + 1);
limit = guys[n].total;
for (int i = 1; i <= n; i++) {
int total = guys[i].total;
int need = guys[i].need;
/// cnt e in ordine ordine descrescatoare
int L = total - need + 1;
int R = total;
int cntL = get(L);
int Lfirst = L, Llast = L;
/// binary search to find them
{
int low = 1, high = L;
while (low <= high) {
int mid = (low + high) / 2;
if (get(mid) == cntL) {
Lfirst = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
}
{
int low = L, high = total;
while (low <= high) {
int mid = (low + high) / 2;
if (get(mid) == cntL) {
Llast = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
}
int cntOfL = Llast - L + 1;
int firstActual = Lfirst;
int lastActual = Lfirst + cntOfL - 1;
add(firstActual, lastActual);
add(Llast + 1, R);
}
int total = 0;
for (int i = 1; i <= limit; i++) {
total += gauss(get(i) - 1);
}
cout << total << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
332 KB |
Output is correct |
2 |
Correct |
11 ms |
3164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
1208 KB |
Output is correct |
2 |
Correct |
67 ms |
828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
1436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
2488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
317 ms |
4324 KB |
Output is correct |
2 |
Correct |
260 ms |
5224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
293 ms |
4436 KB |
Output is correct |
2 |
Correct |
124 ms |
4908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
376 ms |
4672 KB |
Output is correct |
2 |
Correct |
194 ms |
3624 KB |
Output is correct |