| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 431483 | p_square | 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;
#define ll long long
#define int ll
const ll MOD = 1e9+7, INFTY = 1e9+10;
ll pastbig[30], gopro[35], otmul[35];
ll x[1000], y[1000], n;
struct node
{
ll bgnum, mx, prod, lr, rr;
node *lkid, *rkid;
node(ll a, ll b) {lr = a; rr = b;}
node() {}
};
node *rt;
void build_seg(node *cur, ll x[], ll y[])
{
ll l = cur -> lr, r = cur -> rr;
if(l == r)
{
cur -> prod = x[l];
cur -> mx = y[l];
cur -> bgnum = 0;
if(x[l] > 1)
cur -> bgnum = 1;
return;
}
ll mid = (l+r)/2;
cur -> lkid = new node(l, mid);
cur -> rkid = new node(mid+1, r);
build_seg(cur->lkid, x, y);
build_seg(cur->rkid, x, y);
node *lch = cur ->lkid, *rch = cur -> rkid;
cur -> mx = max(lch -> mx, rch -> mx);
cur -> bgnum = lch->bgnum + rch->bgnum;
cur -> prod = lch->prod * rch->prod;
cur->prod %= MOD;
//cout<<l<<" "<<r<<" "<<cur->bgnum<<endl;
}
void update_seg(node *cur, ll x[], ll y[], ll ind)
{
ll l = cur -> lr, r = cur -> rr;
if(l > ind || r < ind)
return;
if(l == r)
{
cur -> prod = x[l];
cur -> mx = y[l];
cur -> bgnum = 0;
if(x[l] > 1)
cur -> bgnum = 1;
return;
}
update_seg(cur->lkid, x, y, ind);
update_seg(cur->rkid, x, y, ind);
node *lch = cur ->lkid, *rch = cur -> rkid;
cur -> mx = max(lch -> mx, rch -> mx);
cur -> bgnum = lch->bgnum + rch->bgnum;
cur -> prod = lch->prod * rch->prod;
cur->prod %= MOD;
//cout<<l<<" "<<r<<" "<<cur->bgnum<<endl;
}
int qmax_seg(node *cur, int ql, int qr)
{
if(cur -> lr > qr || cur -> rr < ql)
return -1;
if(cur -> lr >= ql && cur -> rr <= qr)
return cur -> mx;
int a = qmax_seg(cur->lkid, ql, qr);
int b = qmax_seg(cur->rkid, ql, qr);
return max(a, b);
}
int qprod_seg(node *cur, int ql, int qr)
{
if(cur -> lr > qr || cur -> rr < ql)
return 1;
if(cur -> lr >= ql && cur -> rr <= qr)
return cur -> prod;
int a = qprod_seg(cur->lkid, ql, qr);
int b = qprod_seg(cur->rkid, ql, qr);
return a*b%MOD;
}
int onefy(node *cur, int req)
{
ll l = cur -> lr, r = cur -> rr;
if(cur -> bgnum <= req)
return 0;
if(l == r)
return l;
node *lch = cur ->lkid, *rch = cur -> rkid;
if(rch -> bgnum > req)
return onefy(rch, req);
else
return onefy(lch, req-rch->bgnum);
}
const ll zero = 0;
int find_ans()
{
int prev = n, can = 0, curgo, curmul;
for(int i = 0; i<30; i++)
{
gopro[i] = INFTY;
}
gopro[0] = 1;
curgo = 1;
otmul[0] = qmax_seg(rt, pastbig[0], prev-1);
curmul = otmul[0];
for(int i = 0; i<29; i++)
{
//cout<<gopro[i]<<" "<<otmul[i]<<" "<<pastbig[i]<<endl;
//cout<<curgo<<" "<<curmul<<endl;
gopro[i+1] = gopro[i]*x[pastbig[i]];
if(gopro[i+1] > INFTY)
break;
otmul[i+1] = qmax_seg(rt, pastbig[i+1], pastbig[i]-1);
if(curmul*gopro[i+1] < otmul[i+1]*curgo)
{
curmul = otmul[i+1];
curgo = gopro[i+1];
can = i+1;
}
}
//cout<<can<<" "<<otmul[can]<<endl;
//cout<<qprod_seg(rt, zero, pastbig[can]);
return otmul[can]*qprod_seg(rt, zero, pastbig[can])%MOD;
}
int init(int N, int X[], int Y[])
{
rt = new node(0, N-1);
n = N;
for(int i = 0; i<N; i++)
{
x[i] = X[i];
y[i] = Y[i];
}
build_seg(rt, x, y);
for(int i = 0; i<30; i++)
{
pastbig[i] = onefy(rt, i);
}
return find_ans();
}
int updateX(int pos, int val)
{
//First, update seg
int oldval = x[pos];
x[pos] = val;
update_seg(rt, x, y, pos);
//Now, update pastbig
int onemod = 300;
if(val == 1 && oldval > 1)
{
for(int i = 0; i<30; i++)
{
if(pastbig[i] == pos)
{
onemod = i;
break;
}
}
for(int i = onemod; i<29; i++)
{
pastbig[i] = pastbig[i+1];
}
pastbig[29] = onefy(rt, 29);
}
if(oldval == 1 && val > 1)
{
for(int i = 0; i<30; i++)
{
if(pastbig[i] < pos)
{
onemod = i;
break;
}
}
for(int i = 29; i>onemod; i--)
{
pastbig[i] = pastbig[i-1];
}
if(onemod != 300)
pastbig[onemod] = pos;
//cout<<"MOD"<<onemod<<endl;
}
/*
for(int i = 0; i<10; i++)
{
cout<<pastbig[i]<<" ";
}
*/
return find_ans();
}
int updateY(int pos, int val)
{
y[pos] = val;
update_seg(rt, x, y, pos);
return find_ans();
}