| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 304884 | jainbot27 | 말 (IOI15_horses) | C++17 | 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 <bits/stdc++.h>
// #include "horses.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
using ld = long double;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
// modulo class
int add(int x, int y){ x += y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void ad(int &x, int y) {x = add(x, y);}
int sub(int x, int y){ x -= y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void sb(int &x, int y) {x = sub(x, y);}
int mul(int x, int y){ return ((int64_t)x * (int64_t)y) % MOD; } void ml(int &x, int y) {x = mul(x, y);}
int binpow(int x, int y){ int z = 1; while(y > 0) { if(y % 2 == 1) z = mul(z, x); x = mul(x, x); y /= 2; } return z; }
int inv(int x){ return binpow(x, MOD - 2); }
int divide(int x, int y){ return mul(x, inv(y)); }
template<class node, int T> struct segtree{
int size;
vector<node> vals;
node ne = 0; //a neutral element
node comb(node a, node b){
// cerr << a << " " << b << " " << T << endl;
if(T==0){
// cout << a << " " << b << " " << mul(a, b) << endl;
return mul(a, b);
}
else if(T==1){
return a + b;
}
else{
return max(a, b);
}
}
void init(int n){
size = 1;
while(size < n){
size *= 2;
}
if(T == 1 || T == 2)
vals.assign(2 * size, ne);
else
vals.assign(2*size, 1);
}
void build(vector<node>& a, int x, int lx, int rx){ //build in O(N)
if(rx - lx == 1){
if(lx < (int)a.size()){
vals[x] = a[lx];
}
return;
}
int m = (lx + rx)/2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
vals[x] = comb(vals[2 * x + 1],vals[2 * x + 2]);
}
void build(vector<node>&a){
build(a, 0, 0, size);
}
void update(int i, node v, int x, int lx, int rx){
if(rx - lx == 1){
vals[x] = v;
return;
}
int m = (lx + rx)/2;
if(i < m)
update(i, v, 2 * x + 1, lx, m);
else
update(i, v, 2 * x + 2, m, rx);
vals[x] = comb(vals[2 * x + 1], vals[2 * x + 2]);
}
void update(int i, node v){
update(i, v, 0, 0, size);
}
node query(int l, int r, int x, int lx, int rx){//query the range of [l to r-1]
if(lx >= r || l >= rx) {
if(T==1||T==2)
return ne;
else
return 1;
}
if(lx >= l && rx <= r){
return vals[x];
}
int m = (lx + rx)/2;
node s1 = query(l, r, 2 * x + 1, lx, m);
node s2 = query(l, r, 2 * x + 2, m, rx);
// cerr << "HELLO " << s1 << " " << s2 << " " << T << endl;
return comb(s1, s2);
}
node query(int l, int r){
if(r == -499){
if(T==0){
return 1;
}
else{
return 0;
}
}
// if(T==0) cout << l << " " << r << endl;
return query(l, r, 0, 0, size);
}
};
int n; vi x, y, l, r; vector<ld> lg; segtree<ld, 1> lgs; segtree<int, 0> act; segtree<int, 2> ys;
set<int> vals;
int getANS(){
// cout << "BRUHMOMEN" << endl;
auto it = vals.rbegin();
int i = 0;
ld best = 0; int pos = 0;
while(it!=vals.rend() && i < 35){
int _x = *it;
if(_x == -500) _x=n;
// cout << lgs.query(0, *it+1) << " " << l[_x] << " " << r[_x] << " " << " " << ys.query(l[_x], r[_x]+1) <<" " << log(ys.query(l[_x], r[_x]+1)) << " " << *it << endl;
if(ckmax(best, lgs.query(0, *it+1) + log(ys.query(l[_x], r[_x]+1)))){
pos = *it;
}
i++; it++;
}
// cout << pos << endl;
i = pos;
if(pos == -500) i=n;
return mul(act.query(0, pos+1), ys.query(l[i], r[i]+1));
}
int init(int _n, int _x[], int _y[]){
n = _n; x.resize(n); y.resize(n); lg.resize(n); l.resize(n+1); r.resize(n+1);
F0R(i, n) x[i] = _x[i];
F0R(i, n) y[i] = _y[i];
F0R(i, n){
lg[i] = log(x[i]);
}
lgs.init(n); act.init(n); ys.init(n);
int j = n;
R0F(i, n){
if(x[i] == 1){
}
else{
r[i] = j-1;
l[i] = i;
j = i;
vals.insert(i);
}
}
// trav(x, vals){
// cout << x << ' ';
// }
// cout << endl;
//special case:
l[n] = 0; r[n] = -1;
if(j) {
r[n] = j - 1;
vals.insert(-500);
}
act.build(x); lgs.build(lg); ys.build(y);
// cout << "HELLO WORLD";
// cout << ys.query(0,1) << endl;
int res = getANS();
return res;
}
int updateX(int pos, int val){
}
int updateY(int pos, int val){
}
int main(){
int _n = 3;
int _x[] = {2, 1, 3};
int _y[] = {3, 2, 1};
cout << init(_n, _x, _y) << endl;
}