| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097126 |
2024-10-06T07:28:26 Z |
Whisper |
Sails (IOI07_sails) |
C++17 |
|
121 ms |
8276 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define MAX 100005
int nArr;
struct Sail{
int height, flag;
Sail(){}
Sail(int _height, int _flag): height(_height), flag(_flag){}
bool operator < (const Sail& o) const{
return height < o.height;
}
} A[MAX];
struct SegmentTree{
vector<int> st, lz;
int n;
SegmentTree(int _n = 0){
this -> n = _n;
st.resize((n << 2) + 5);
lz.resize((n << 2) + 5);
}
#define lson (nd << 1)
#define rson (nd << 1 | 1)
void pushDown(int nd){
if(!lz[nd]) return;
st[lson] += lz[nd];
st[rson] += lz[nd];
lz[lson] += lz[nd];
lz[rson] += lz[nd];
lz[nd] = 0;
}
void upd(int nd, int l, int r, int u, int v, int value){
if (u > r || v < l) return;
if (u <= l && v >= r) {
st[nd] += value;
lz[nd] += value;
return;
}
pushDown(nd);
int m = (l + r) >> 1;
upd(lson, l, m, u, v, value);
upd(rson, m + 1, r, u, v, value);
st[nd] = max(st[lson], st[rson]);
}
int query(int nd, int l, int r, int u, int v){
if (u > r || v < l) return 0;
if (u <= l && v >= r) return st[nd];
int m = (l + r) >> 1;
pushDown(nd);
int ql = query(lson, l, m, u, v);
int qr = query(rson, m + 1, r, u, v);
return max(ql, qr);
}
int findLeft(int value, int nd, int l, int r){
if(st[1] <= value) return 1;
if (l == r){
return l + 1;
}
int m = (l + r) >> 1;
pushDown(nd);
if(st[rson] > value){
return findLeft(value, rson, m + 1, r);
}
return findLeft(value, lson, l, m);
}
int findRight(int value, int nd, int l, int r){
if (l == r){
return l;
}
int m = (l + r) >> 1;
pushDown(nd);
if(st[rson] >= value){
return findRight(value, rson, m + 1, r);
}
return findRight(value, lson, l, m);
}
int findLeft(int value){
return findLeft(value, 1, 1, n);
}
int findRight(int value){
return findRight(value, 1, 1, n);
}
void upd(int l, int r, int v){
upd(1, 1, n, l, r, v);
}
int query(int l, int r){
return query(1, 1, n, l, r);
}
};
void process(void){
cin >> nArr;
int lim = 0;
for (int i = 1; i <= nArr; ++i){
cin >> A[i].height >> A[i].flag;
maximize(lim, A[i].height);
}
sort(A + 1, A + nArr + 1);
SegmentTree myit(lim + 5);
for (int i = 1; i <= nArr; ++i){
int value = myit.query(A[i].height - A[i].flag + 1, A[i].height - A[i].flag + 1);
int L = myit.findLeft(value);
int R = myit.findRight(value);
if(R > lim){
myit.upd(L, min(lim, L + A[i].flag - 1), 1);
}
else{
myit.upd(R + 1, A[i].height, 1);
myit.upd(L, L + A[i].flag - A[i].height + R - 1, 1);
}
}
int ans = 0;
for (int i = 1; i <= lim; ++i){
int value = myit.query(i, i);
ans += value * (value - 1) / 2;
}
cout << ans;
}
signed main(){
#define name "Whisper"
cin.tie(nullptr) -> sync_with_stdio(false);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
process();
return (0 ^ 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
12 ms |
6600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
19 ms |
1188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
4188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
76 ms |
7900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
8024 KB |
Output is correct |
| 2 |
Correct |
50 ms |
7260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
63 ms |
3944 KB |
Output is correct |
