# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
709901 | 2023-03-14T19:01:59 Z | ssense | Horses (IOI15_horses) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "horses.h" using namespace std; #define MOD 1000000009 int ng; vector<int> xg; vector<int> yg; int init(int n, int[] x, int[] y) { ng = n; for(int i = 0; i < n; i++) { xg.push_back(x[i]); yg.push_back(y[i]); } int produs = 1; int now = ng-1; for(; now >= 0; now--) { produs*=xg[now]; if(produs >= 1e9) { break; } } now = max(now, 0); long long mx = 0, idx = 0; int pr = 1; for(int i = now; i < ng; i++) { pr*=xg[i]; if(mx < pr*yg[i]) { mx = pr*yg[i]; idx = i; } } mx%=MOD; for(int i = 0; i < idx-1; i++) { mx*=xg[i]; mx%=MOD; } return (int)mx; } int updateX(int pos, int val) { xg[pos] = val; int produs = 1; int now = ng-1; for(; now >= 0; now--) { produs*=xg[now]; if(produs >= 1e9) { break; } } now = max(now, 0); long long mx = 0, idx = 0; int pr = 1; for(int i = now; i < ng; i++) { pr*=xg[i]; if(mx < pr*yg[i]) { mx = pr*yg[i]; idx = i; } } mx%=MOD; for(int i = 0; i < idx-1; i++) { mx*=xg[i]; mx%=MOD; } return (int)mx; } int updateY(int pos, int val) { yg[pos] = val; int produs = 1; int now = ng-1; for(; now >= 0; now--) { produs*=xg[now]; if(produs >= 1e9) { break; } } now = max(now, 0); long long mx = 0, idx = 0; int pr = 1; for(int i = now; i < ng; i++) { pr*=xg[i]; if(mx < pr*yg[i]) { mx = pr*yg[i]; idx = i; } } mx%=MOD; for(int i = 0; i < idx-1; i++) { mx*=xg[i]; mx%=MOD; } return (int)mx; }