Submission #1184780

#TimeUsernameProblemLanguageResultExecution timeMemory
1184780countlessHorses (IOI15_horses)C++20
100 / 100
163 ms75836 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 1e9+7; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); int n; vector<ll> x, y; struct segtree { int l, r; double num, price; ll modNum, modPrice; segtree *left, *right; void merge() { num = left->num + right->num; modNum = left->modNum * right->modNum; modNum %= MOD; if (left->price >= left->num + right->price) { price = left->price; modPrice = left->modPrice; } else { price = left->num + right->price; modPrice = left->modNum * right->modPrice; modPrice %= MOD; } } segtree(int l, int r, vector<ll> &x, vector<ll> &y) : l(l), r(r) { if (l == r) { left = right = nullptr; num = log10(x[l]), modNum = x[l]; price = num + log10(y[l]), modPrice = modNum * y[l], modPrice %= MOD; return; } int m = (l+r)/2; left = new segtree(l, m, x, y); right = new segtree(m+1, r, x, y); merge(); } void update(int ind) { if (l == r) { num = log10(x[l]), modNum = x[l]; price = num + log10(y[l]), modPrice = modNum * y[l], modPrice %= MOD; return; } int m = (l+r)/2; if (ind <= m) left->update(ind); else right->update(ind); merge(); } }; segtree *st; int init(int N, int X[], int Y[]) { n = N; x.resize(n), y.resize(n); REP(i, 0, n) { x[i] = X[i]; y[i] = Y[i]; } st = new segtree(0, n-1, x, y); return st->modPrice; } int updateX(int pos, int val) { x[pos] = val; st->update(pos); return st->modPrice; } int updateY(int pos, int val) { y[pos] = val; st->update(pos); return st->modPrice; } // signed main() { // int n; cin >> n; // int x[n], y[n]; // REP(i, 0, n) // cin >> x[i]; // REP(i, 0, n) // cin >> y[i]; // cout << init(n, x, y) << endl; // int q; cin >> q; // while (q--) { // int command; cin >> command; // int ind, upd; cin >> ind >> upd; // if (command == 1) { // cout << updateX(ind, upd) << endl; // } else { // cout << updateY(ind, upd) << endl; // } // } // return 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...