# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
919775 |
2024-02-01T15:52:17 Z |
penguin133 |
Sails (IOI07_sails) |
C++17 |
|
214 ms |
17232 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
pi H[100005];
priority_queue <int, vector <int>, greater <int> > pq;
struct node{
int s, e, m, val, lz;
node *l, *r;
node(int _s, int _e){
s = _s, e= _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
val = lz = 0;
}
void prop(){
if(lz){
val += lz * (e - s + 1);
if(s != e)l->lz += lz, r->lz += lz;
lz = 0;
}
}
void upd(int a, int b, int c){
if(a == s && b == e)lz += c;
else{
if(b <= m)l->upd(a, b, c);
else if(a > m)r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m+1, b, c);
l->prop(), r->prop();
val = l->val + r->val;
}
}
int qry(int a, int b){
prop();
if(a == s && b == e)return val;
if(b <= m)return l->qry(a, b);
if(a > m)return r->qry(a, b);
return l->qry(a, m) + r->qry(m+1, b);
}
}*root;
void solve(){
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++)cin >> H[i].fi >> H[i].se;
sort(H + 1, H + n + 1);
set <int> changing;
root = new node(0, 100005);
root->upd(0, 0, 1);
for(int i = 1; i <= n; i++){
if(H[i].fi > H[i - 1].fi && root->qry(H[i - 1].fi, H[i - 1].fi))changing.insert(H[i - 1].fi + 1);
auto it = changing.lower_bound(H[i].fi - H[i].se + 1);
int tmp = H[i].fi + 1;
if(it != changing.end()){
tmp = *it;
//cerr << tmp << ' ';
ans += root->qry(tmp, H[i].fi);
root->upd(tmp, H[i].fi, 1);
}
if(it != changing.begin()){
it--;
int tmp2 = *it;
int leftover = H[i].se - (H[i].fi - tmp + 1);
if(leftover){
//cerr << tmp2 << ' ' << leftover;
ans += root->qry(tmp2, tmp2 + leftover - 1);
root->upd(tmp2, tmp2 + leftover - 1, 1);
//update the changing points
if(tmp2 != 1 && root->qry(tmp2, tmp2) == root->qry(tmp2 - 1, tmp2 - 1))changing.erase(tmp2);
if(tmp2 + leftover != 1 && root->qry(tmp2 + leftover, tmp2 + leftover) < root->qry(tmp2 + leftover - 1, tmp2 + leftover - 1))changing.insert(tmp2 + leftover);
}
}
//cout << '\n';
if(tmp > 1 && tmp != H[i].fi + 1 && root->qry(tmp, tmp) == root->qry(tmp - 1, tmp - 1))changing.erase(tmp);
}
cout << ans;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
sails.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
91 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12888 KB |
Output is correct |
2 |
Correct |
8 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12888 KB |
Output is correct |
2 |
Correct |
8 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12888 KB |
Output is correct |
2 |
Correct |
8 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12888 KB |
Output is correct |
2 |
Correct |
8 ms |
13144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12888 KB |
Output is correct |
2 |
Correct |
10 ms |
12888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
13144 KB |
Output is correct |
2 |
Correct |
50 ms |
13912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
14936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
14600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
15164 KB |
Output is correct |
2 |
Correct |
145 ms |
15700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
17232 KB |
Output is correct |
2 |
Correct |
67 ms |
14928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
16024 KB |
Output is correct |
2 |
Correct |
128 ms |
15604 KB |
Output is correct |