# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
773298 |
2023-07-04T20:06:59 Z |
rominanafu |
Sails (IOI07_sails) |
C++11 |
|
253 ms |
3828 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ura {
ll h, k;
};
ll n, tam;
ura masts[100005];
ll ST[400009];
bool cmp(const ura &a, const ura &b) {
return a.h < b.h;
}
void actualizar(ll pos, int val, ll nodo=1, ll ini=1, ll fin=100001) {
if (pos < ini || pos > fin)
return;
if (ini == fin) {
ST[nodo] += val;
return;
}
ll mid = (ini+fin) / 2;
actualizar(pos, val, nodo*2, ini, mid);
actualizar(pos, val, nodo*2+1, mid+1, fin);
ST[nodo] = ST[nodo*2] + ST[nodo*2+1];
}
ll suma(ll pos, ll nodo=1, ll ini=1, ll fin=100001) {
if (pos < ini)
return 0;
if (pos >= fin)
return ST[nodo];
ll s=0;
ll mid = (ini + fin) / 2;
s += suma(pos, nodo*2, ini, mid);
s += suma(pos, nodo*2+1, mid+1, fin);
return s;
}
ll posicion_menor(ll &num) {
ll izq=1, der=100001, mid, r=0;
while (izq <= der) {
mid = (izq+der) / 2;
if (suma(mid) < num) {
r = mid;
der = mid-1;
} else {
izq = mid+1;
}
}
return r;
}
ll posicion_igual(ll &num) {
ll izq=1, der=100001;
ll mid, r=0;
while (izq <= der) {
mid = (izq+der) / 2;
if (suma(mid) > num) {
izq = mid+1;
} else {
der = mid-1;
r = mid;
}
}
return r;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(ll i=0; i<n; i++) {
cin >> masts[i].h >> masts[i].k;
tam = max(tam, masts[i].h);
}
sort(masts, masts+n, cmp);
ll pos_menor, pos_igual, s;
for(ll i=0; i<n; i++) {
s = suma(masts[i].h - masts[i].k + 1);
pos_menor = posicion_menor(s);
pos_igual = posicion_igual(s);
if (s != 0) {
///para pos_menor:
actualizar(pos_menor, 1);
actualizar(masts[i].h + 1, -1);
masts[i].k -= masts[i].h + 1 - pos_menor;
}
///para pos_igual:
actualizar(pos_igual, 1);
actualizar(pos_igual + masts[i].k, -1);
}
ll resp=0;
for(ll i=0; i<=masts[n-1].h; i++) {
s = suma(i);
resp += (s * (s - 1)) / 2;
}
cout << resp;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
468 KB |
Output is correct |
2 |
Correct |
9 ms |
2388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
980 KB |
Output is correct |
2 |
Correct |
56 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
1436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
2112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
3524 KB |
Output is correct |
2 |
Correct |
182 ms |
3536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
3772 KB |
Output is correct |
2 |
Correct |
169 ms |
3496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
3828 KB |
Output is correct |
2 |
Correct |
196 ms |
2532 KB |
Output is correct |