# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
885456 |
2023-12-09T19:01:18 Z |
codexistent |
Sails (IOI07_sails) |
C++14 |
|
49 ms |
2896 KB |
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define RFOR(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
struct RangeFenwick {
vector<int> bit[2];
int size;
RangeFenwick(int n){
size = n + 1;
bit[0].assign(size + 1, 0), bit[1].assign(size + 1, 0);
}
void add(bool t, int i, int x){
for(; i < size; i += i & -i) bit[t][i] += x;
}
void range_add(int l, int r, int x){
add(0, l, x), add(0, r + 1, -x);
add(1, l, x * (l - 1)), add(1, r + 1, -x * r);
}
int pfx_helper(int t, int i){
int r = 0;
for(; i > 0; i -= i & -i) r += bit[t][i];
return r;
}
int pfx(int i){
return pfx_helper(0, i)*i - pfx_helper(1, i);
}
int pt(int i){
return pfx(i) - pfx(i - 1);
}
};
int main(){
int N;
cin >> N;
pair<int, int> M[N];
FOR(i, 0, N - 1){
int h, s;
cin >> h >> s;
M[i] = make_pair(h, s);
}
sort(M, M + N);
RangeFenwick T(N);
FOR(i, 0, N - 1){
int H = M[i].first, S = M[i].second;
int PM = T.pt(H - S + 1); // prev max sail
/*int a = 1, b = H; // a = lowest index with value <= PM
while(a < b){
int m = (a + b) / 2;
if(PM >= T.pt(m)){
b = m;
}else{
a = m + 1;
}
}*/
int a2 = 1, b2 = H; // a2 = highest index w value <= PM
while(a2 < b2){
int m = (a2 + b2 + 1) / 2;
if(PM <= T.pt(m)){
a2 = m;
}else{
b2 = m - 1;
}
}
break;
//if(a2 != H) T.range_add(a2 + 1, H, 1);
//T.range_add(a, a2 - (H - S + 1 - a), 1);
}
/*ll R = 0, r = 0, p = -1;
RFOR(i, N, 1) if(T.pt(i) != 0) {
if(T.pt(i) - 1 != p) {
r += T.pt(i) - 1;
p = T.pt(i) - 1;
}
R += r;
}
cout << R << endl;*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
1072 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
44 ms |
2896 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
45 ms |
1632 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
1876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |