제출 #1097125

#제출 시각아이디문제언어결과실행 시간메모리
1097125vjudge1Sails (IOI07_sails)C++17
100 / 100
118 ms9428 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...