Submission #1033869

#TimeUsernameProblemLanguageResultExecution timeMemory
1033869daodaSails (IOI07_sails)C++17
0 / 100
46 ms1884 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define FOR(x, a, b) for(ll x=a;x < ll(b); x++) #define endl '\n' #define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++) using namespace std; // using namespace __gnu_pbds; typedef unsigned long long int ull; typedef long long int ll; typedef vector<ll> vll; typedef pair<ll,ll> pll; typedef vector<pll> vpll; typedef vector<bool> vb; typedef vector<char> vc; typedef vector<int> vi; typedef pair<int, int> pi; typedef vector<pi> vpi; typedef vector<short> vs; typedef long double ld; // template <class T> // using Tree = // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll INF = ll(1e9) + 10; const ll INIT = 7; const ll MAX_VAL = 50; const ll MAX_SZ = (ll) 1e4; const ll MAX_N = 20; const ll MAX_M = MAX_N; const long double eps = 1e-4; const ll MOD = ll(1e9) + 7; vi rd = {0, 1, 0, -1}, cd = {1, 0, -1, 0}; ll add(ll a, ll b) { return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD; } ll mult(ll a, ll b) { return (((a % MOD) * (b % MOD)) + MOD) % MOD; } ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); } const int MAX_H = 1e5; struct BIT { vll tree; int sz; BIT(int inp_sz) { sz = inp_sz; tree.resize(sz + 1, 0); } void add(int ind, ll val) { while(ind <= sz) { tree[ind] += val; ind += ind & -ind; } } ll pref_sum(int ind) { ll sum = 0; while(ind >= 1) { sum += tree[ind]; ind -= ind & -ind; } return sum; } ll sum(int a, int b) { return pref_sum(b) - pref_sum(a - 1); } void set(int ind, ll val) { add(ind, val - sum(ind, ind)); } void addrange(int l, int r, ll val) { add(l, val); if(r < sz) add(r + 1, -val); } }; int main() { // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); fast // TESTCASE { // } int n; cin >> n; vpi inp(n); FOR(i, 0, n) cin >> inp[i].first >> inp[i].second; sort(inp.begin(), inp.end()); BIT bit1(MAX_H); FOR(i, 0, n) { int height = inp[i].first, sails = inp[i].second; int lb = 1, upb = height - sails + 1; // cout << lb << " " << upb << endl; while(lb < upb) { int mid = (upb + lb) / 2; if(bit1.pref_sum(mid) == bit1.pref_sum(height)) upb = mid; else lb = mid + 1; // cout << lb << " " << upb << endl; } bit1.addrange(upb, upb + sails - 1, 1); // cout << bit1.pref_sum(100) << endl; // cout << "e" << endl; } ll ans = 0; FOR(i, 1, MAX_H + 1) { ll cur_val = max(bit1.pref_sum(i) - 1, 0ll); ans += (cur_val * (cur_val + 1)) / 2ll; } cout << ans; }
#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...