# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
119047 |
2019-06-20T08:21:58 Z |
nvmdava |
Sails (IOI07_sails) |
C++17 |
|
325 ms |
3824 KB |
#include <bits/stdc++.h>
using namespace std;
int tree[100005], lazy[400005];
vector<pair<int, int> > v;
void update(int id, int l, int r, int L, int R){
if(l == L && r == R){
lazy[id]++;
return;
}
int m = (l + r) >> 1;
if(m < L) update(id << 1 | 1, m + 1, r, L, R);
else if(m >= R) update(id << 1, l, m, L, R);
else {
update(id << 1, l, m, L, m);
update(id << 1 | 1, m + 1, r, m + 1, R);
}
}
void push(int id, int l, int r){
if(l == r) tree[l] += lazy[id];
else {
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
int query(int id, int l, int r, int x){
push(id, l, r);
if(l == r) return tree[l];
int m = (l + r) >> 1;
if(m < x) return query(id << 1 | 1, m + 1, r, x);
return query(id << 1, l, m, x);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i = 1; i <= n; i++){
int h, k;
cin>>h>>k;
v.push_back({h, k});
}
sort(v.begin(), v.end());
for(auto& x : v){
int h = x.first;
int k = x.second;
int idr = h - k + 1;
int idl = idr;
int val = query(1, 1, 100000, idr);
for(int j = 19; j >= 0; j--){
if(idl - (1 << j) > 0 && query(1, 1, 100000, idl - (1 << j)) == val) idl -= (1 << j);
if(idr + (1 << j) <= h && query(1, 1, 100000, idr + (1 << j)) == val) idr += (1 << j);
}
int ri = h - idr;
int le = k - ri;
if(le) update(1, 1, 100000, idl, idl + le - 1);
if(ri) update(1, 1, 100000, idr + 1, idr + ri);
}
long long res = 0;
for(int i = 1; i <= 100000; i++){
long long a = query(1, 1, 100000, i);
res += a * (a - 1) / 2;
}
cout<<res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1920 KB |
Output is correct |
2 |
Correct |
9 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1792 KB |
Output is correct |
2 |
Correct |
9 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1792 KB |
Output is correct |
2 |
Correct |
9 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1792 KB |
Output is correct |
2 |
Correct |
10 ms |
1764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1792 KB |
Output is correct |
2 |
Correct |
14 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
1912 KB |
Output is correct |
2 |
Correct |
66 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
2128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
2248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
2560 KB |
Output is correct |
2 |
Correct |
203 ms |
3440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
2596 KB |
Output is correct |
2 |
Correct |
114 ms |
3308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
2816 KB |
Output is correct |
2 |
Correct |
183 ms |
3824 KB |
Output is correct |