Submission #1158504

#TimeUsernameProblemLanguageResultExecution timeMemory
1158504zhasynHorses (IOI15_horses)C++20
17 / 100
1595 ms8252 KiB
#include <bits/stdc++.h> #include "horses.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define pf push_front using namespace std; using namespace __gnu_pbds; #define F first #define S second typedef long long ll; #define pii pair <int, int> #define pll pair <ll, ll> typedef long double ld; const ll N = 5 * 1e5 + 100, M = 2 * 1e6 + 100, len = 21, inf = 1e18; const ll mod = 1e9 + 7; ll um(ll a, ll b){ return (1LL * a * b) % mod; } ll subr(ll a, ll b){ return ((1LL * a - b) % mod + mod) % mod; } typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>o_set; int x[N], p[N], n; ll calc(){ int j = n - 1, mx = p[n - 1] * x[n - 1]; for(int i = n - 2; i >= 0; i--){ if(mx > 1e9) break; if(p[i] > mx) j = i; mx = max(mx, p[i]) * x[i]; } ll xx =1; for(int i = 0; i <= j; i++){ xx = um(xx, x[i]); } return um(xx, p[j]); } int init(int nx, int xx[], int pp[]) { n = nx; for(int i = 0; i < n; i++){ x[i] = xx[i]; p[i] = pp[i]; } return calc(); } int updateX(int pos, int val) { x[pos] = val; return calc(); } int updateY(int pos, int val) { p[pos] = val; return calc(); }
#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...