| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 899375 |
2024-01-05T23:42:17 Z |
sverma22 |
Sails (IOI07_sails) |
C++17 |
|
2 ms |
856 KB |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int MAXN = 1e5 + 5;
int n;
int seg[4 * MAXN];
// highkey this is all useless let's j not call it
void build(int node = 1, int l = 1, int r = MAXN) {
if(l == r) {
seg[node] = 0; // normally you do a[l] or whatever not rlly necessary
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
seg[node] = seg[2 * node] + seg[2 * node + 1];
}
// point update alr bet getting a lil used to this segtree shit
void upd(int x, int val, int node = 1, int l = 1, int r = MAXN) {
if(l == r) { // should be when l == r == x
seg[node] += val;
return;
}
int mid = (l + r) / 2;
if(x > mid) upd(x, val, 2 * node + 1, mid + 1, r);
else upd(x, val, 2 * node, l, mid);
seg[node] = seg[2 * node] + seg[2 * node + 1];
}
// i love hte library
// query will j give the prefix sum
// same as query of [l, r] 1 - x [l, r]
int query(int x, int node = 1, int l = 1, int r = MAXN) {
// case 1 completely outside
if(x < l || r < 1) {
return 0;
}
// case 2 completely inside
if(1 <= l && r <= x) {
return seg[node];
}
// case 3 recurse
int mid = (l + r) / 2;
int lr = query(x, 2 * node, l, mid);
int rr = query(x, 2 * node + 1, mid + 1, r);
return lr + rr;
}
// shit should be right
int numGreaterThan(int x, int bound) { // 2 [3, 3]
// a special case for fucking 0 then
if(query(1) <= x) return 0; // yes i have an extra case too
int l = 1, r = bound;
while(l < r) {
int mid = (l + r + 1) / 2; // [3, 1] 2 -> answer should be 1 [3, 3] -> should should be 2
int res = query(mid); // 3 then u get fucking stuck
if(res <= x) {
r = mid - 1; // we don't even like mid [garunteed progress]
} else {
l = mid;
}
}
return l;
}
void solve() {
cin >> n;
vector<pair<int, int> > sails(n);
for(int i = 0; i < n; i++) cin >> sails[i].first >> sails[i].second;
sort(sails.begin(), sails.end());
// ah no need for lazy prop if it's done difference array style and then j doing range queries
for(auto &[height, num] : sails) {
int val = query(height - num + 1);
int r = numGreaterThan(val - 1, height);
int l = numGreaterThan(val, height); // 3 3 2 1 0
// embarasing i can't implement a binary search that clearnly
int numSameToUpd = r - height + num;
upd(l + 1, 1);
upd(l + numSameToUpd + 1, -1);
if(r + 1 <= height) {
upd(r + 1, 1);
upd(height + 1, -1);
}
// for(int i = 1; i <= height; i++) {
// int res = query(i);
// cout << res << ' ';
// }
// cout << '\n';
}
// that's it though
int ans = 0;
for(int i = 1; i <= sails[n - 1].first; i++) {
int res = query(i);
ans += (res * (res - 1)) / 2;
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("file.txt", "r", stdin);
#endif
int t = 1; // cin >> t;
while(t--) {
solve();
}
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:115:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | freopen("file.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
