| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 533218 | ivan24 | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
const ll INF = 1e18+10;
const ll MOD = 1e9+7;
const ll MX_VAL = 1e9;
struct stnode {
ll prod,mx;
stnode (){ prod = 1; mx = 0; }
stnode merge_node (const stnode& rhs){
stnode res;
res.prod = prod*rhs.prod; res.prod %= MOD;
res.mx = max(mx,rhs.mx);
return res;
}
};
ll modpow (ll b, ll e){
ll res = 1;
while (e > 0){
if (e%2) res *= b;
e /= 2; b *= b;
res %= MOD; b %= MOD;
}
return res;
}
struct frac {
ll n,d;
frac(){ n = 1; d = 1;}
frac (ll _n, ll _d){
n = _n; d = _d;
}
bool operator>(const frac& rhs) const{
return n*rhs.d > rhs.n*d;
}
bool operator<(const frac& rhs) const{
return n*rhs.d < rhs.n*d;
}
ll mult (ll x){
x *= n; x %= MOD;
x *= modpow(d,MOD-2); x %= MOD;
return x;
}
};
class SegTree {
private:
vector<stnode> st;
ll n;
vi a,b;
ll left(ll x){ return (x << 1); }
ll right(ll x){ return ((x << 1) + 1); }
void build (ll i, ll l, ll r){
if (l == r){
st[i].prod = a[i];
st[i].mx = b[i];
}else{
ll m = (l+r)/2;
build(left(i),l,m);
build(right(i),m+1,r);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
stnode query (ll i, ll l, ll r, ll ql, ll qr){
if (qr >= r && l >= ql){
return st[i];
}else if (l > qr || ql > r){
return stnode();
}else{
ll m = (l+r)/2;
stnode lres = query(left(i),l,m,ql,qr);
stnode rres = query(right(i),m+1,r,ql,qr);
return lres.merge_node(rres);
}
}
void update (ll i, ll l, ll r, ll type, ll val, ll idx){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r >= idx && idx >= l){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r == l){
if (type == 0) st[i].prod = val;
else st[i].mx = val;
}else{
ll m = (l+r)/2;
update(left(i),l,m,type,val,idx);
update(right(i),m+1,r,type,val,idx);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
}
public:
SegTree (vi _a, vi _b): a(_a), b(_b){
n = a.size();
st.resize(4*n);
build(1,0,n-1);
}
SegTree(ll _n){
n = _n;
a.assign(n,1);
b.assign(n,0);
st.assign(4*n,stnode());
}
SegTree(){}
ll query (ll type, ll l, ll r){
stnode res;
//cout << "queried: " << type << " " << l << " " << r << endl;
if (r >= l) res = query(1,0,n-1,l,r);
if (type == 0) return res.prod;
else return res.mx;
}
void update (ll type, ll val, ll idx){
//cout << "update: " << type << " " << val << " " << idx << endl;
//cout << n << endl;
update (1,0,n-1,type,val,idx);
}
};
class WeirdDS {
private:
SegTree st;
vi x,y;
set<ll> overone;
ll n;
public:
WeirdDS(int _n){
n = _n;
st = SegTree(n);
x.assign(n,1);
y.assign(n,0);
set<ll>().swap(overone);
overone.insert(0);
}
WeirdDS(){}
ll updateX(ll pos, ll val){
st.update(0,val,pos);
if (val == 1){
auto itr = overone.find(-pos);
if (itr != overone.end())
overone.erase(itr);
}else{
overone.insert(-pos);
}
overone.insert(0);
x[pos] = val;
return query();
}
ll updateY(ll pos, ll val){
st.update(1,val,pos);
y[pos] = val;
return query();
}
ll query (){
bool broke = false;
ll prv = n;
ll ctr = 1;
frac maxMult;
for (auto i: overone){
ll bigY = st.query(1,-i,prv-1);
frac curMult = frac(bigY,ctr);
if (curMult > maxMult) maxMult = curMult;
prv = -i;
ctr *= x[-i];
if (x[-i] == 1) return INF;
if (ctr > MX_VAL) break;
}
return maxMult.mult(st.query(0,0,n-1));
}
};
WeirdDS myDS;
int init(int n, int x[], int y[]) {
//cout.setstate(ios_base::failbit);
myDS = WeirdDS(n);
for (ll i = 0; n > i; i++){
myDS.updateX(i,x[i]);
myDS.updateY(i,y[i]);
}
////cout << myDS.query() << endl;
return myDS.query();
}
int updateX(int pos, int val) {
//cout << "updateX: " << pos << " " << val << endl;
int res = myDS.updateX(pos,val);
//cout << res << endl;
return res;
}
int updateY(int pos, int val) {
//cout << "updateY: " << pos << " " << val << endl;
int res = myDS.updateY(pos,val);
//cout << res << endl;
return res;
}
#include "horses.h"
#include <stdio.h>
#include <stdlib.h>
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main() {
_inputFile = fopen("horses.in", "rb");
_outputFile = fopen("horses.out", "w");
int N; N = _readInt();
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
X[i] = _readInt();
}
for (int i = 0; i < N; i++) {
Y[i] = _readInt();
}
fprintf(_outputFile,"%d\n",init(N,X,Y));
int M; M = _readInt();
for (int i = 0; i < M; i++) {
int type; type = _readInt();
int pos; pos = _readInt();
int val; val = _readInt();
if (type == 1) {
fprintf(_outputFile,"%d\n",updateX(pos,val));
} else if (type == 2) {
fprintf(_outputFile,"%d\n",updateY(pos,val));
}
}
return 0;
}