# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
849343 |
2023-09-14T14:01:39 Z |
phoenix0423 |
Sails (IOI07_sails) |
C++17 |
|
82 ms |
4624 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define all(v) v.begin(), v.end()
const int maxn = 1e5 + 5;
int BIT[maxn];
void upd(int pos, int val){
pos++;
while(pos < maxn){
BIT[pos] += val;
pos += lowbit(pos);
}
}
int qry(int pos){
pos++;
int ret = 0;
while(pos > 0){
ret += BIT[pos];
pos -= lowbit(pos);
}
return ret;
}
struct info{
int h, k;
info(){}
info(int _h, int _k) : h(_h), k(_k){}
bool operator < (const info& other) const{
return h < other.h || (h == other.h && k < other.k);
}
};
istream &operator>>(istream &s, info & q){
s >> q.h >> q.k;
return s;
}
int main(void){
// fastio;
int n;
cin>>n;
vector<info> a(n);
for(int i = 0; i < n; i++) cin>>a[i];
sort(a.begin(), a.end());
set<int> s;
s.insert(0);
for(int i = 0; i < n; i++){
auto [h, k] = a[i];
auto idx = s.upper_bound(h - k);
idx--;
//idx = first change point smaller than h - k
if(idx == prev(s.end())){
int x = *idx;
if(qry(x) == 1) s.erase(idx);
s.insert(x + k);
upd(x + 1, 1);
upd(x + k + 1, -1);
}
else if(*idx == h - k){
upd(h - k + 1, 1);
upd(h + 1, -1);
if(*idx != 0) s.erase(idx);
if(h != a[i - 1].h) s.insert(h);
}
else{
auto nxt = next(idx);
upd(*nxt + 1, 1);
upd(h + 1, -1);
int left = k - (h - *nxt);
upd(*idx + 1, 1);
upd(*idx + left + 1, -1);
s.insert(*idx + left);
if(h != a[i - 1].h) s.insert(h);
if(qry(*nxt + 1) == qry(*nxt)) s.erase(nxt);
if(*idx != 0) s.erase(idx);
}
}
ll pre = 0;
ll ans = 0;
for(auto x : s){
ll cnt = qry(x);
ans += (x - pre) * cnt * (cnt - 1) / 2;
pre = x;
}
cout<<ans<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
368 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 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 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
2276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
41 ms |
2028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
2624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
4624 KB |
Output is correct |
2 |
Correct |
49 ms |
2128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
3412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |