Submission #823424

#TimeUsernameProblemLanguageResultExecution timeMemory
823424_martynasHorses (IOI15_horses)C++11
20 / 100
379 ms49316 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #warning change mxn const int mxn = 5e5+5; const int mxval = 1e9; const int mod = 1e9+7; struct Seg { int mx[4*mxn]; int get(int u, int l, int r, int ql, int qr) { if(qr < l || r < ql) return 0; if(ql <= l && r <= qr) return mx[u]; int m = (l+r)/2; return max(get(2*u, l, m, ql, qr), get(2*u+1, m+1, r, ql, qr)); } void set(int u, int l, int r, int i, int x) { if(l == r) { mx[u] = x; return; } int m = (l+r)/2; if(i <= m) set(2*u, l, m, i, x); else set(2*u+1, m+1, r, i, x); mx[u] = max(mx[2*u], mx[2*u+1]); } } seg; int n; int x[mxn], y[mxn]; set<int> st; ll tot = 1; ll mod_pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans*a%mod; a = a*a%mod; b >>= 1; } return ans; } int get(); int init(int N, int X[], int Y[]) { n = N; copy(X, X+n, x); copy(Y, Y+n, y); for(int i = 0; i < N; i++) seg.set(1, 0, n-1, i, Y[i]); st.insert(n); for(int i = n-1; i >= 0; i--) { if(X[i] > 1) { tot = tot*X[i]%mod; st.insert(i); } } return get(); } int get() { ll acc = 1; int last = -1; auto rit = next(st.rbegin()); while(rit != st.rend()) { acc *= x[*rit]; last = *rit; if(acc > mxval) break; rit = next(rit); } auto it = st.lower_bound(last); ll mx = 0; acc = 1; while(next(it) != st.end()) { int i = *it; int j = *next(it); if(i != last) acc = acc*x[i]; ll best_y = seg.get(1, 0, n-1, i, j-1); mx = max(mx, acc*best_y); it = next(it); } //printf("mx = %lld\n", mx); mx %= mod; return tot*mod_pow(acc, mod-2)%mod*mx%mod; } int updateX(int pos, int val) { tot = tot*mod_pow(x[pos], mod-2)%mod; x[pos] = val; tot = tot*val%mod; if(val > 1) st.insert(pos); else (st.erase(pos)); return get(); } int updateY(int pos, int val) { seg.set(1, 0, n-1, pos, val); return get(); } // int main(int argc, char const *argv[]) // { // int N; // cin >> N; // int X[N], Y[N]; // for(int i = 0; i < N; i++) cin >> X[i]; // for(int i = 0; i < N; i++) cin >> Y[i]; // cout << "init: " << init(N, X, Y) << "\n"; // int M; // cin >> M; // for(int i = 0; i < M; i++) { // int type; cin >> type; // int pos, val; cin >> pos >> val; // if(type == 1) { // cout << "resp: " << updateX(pos, val) << "\n"; // } // else { // cout << "resp: " << updateY(pos, val) << "\n"; // } // } // return 0; // }

Compilation message (stderr)

horses.cpp:8:2: warning: #warning change mxn [-Wcpp]
    8 | #warning change mxn
      |  ^~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:83:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   83 |  return tot*mod_pow(acc, mod-2)%mod*mx%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
#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...