| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 523609 | Lobo | Horses (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;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 550000
int n, a[maxn], b[maxn], trmx[4*maxn], trp[4*maxn];
map<int,pair<int,int>> lr;
int mod = 1e9 + 7;
dbl logmax, logtot;
void attmx(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
else if(l == r) trmx[no] = val;
else {
int f1 = 2*no;
int f2 = 2*no + 1;
int mid = (l+r)>>1;
attmx(f1,l,mid,pos,val);
attmx(f2,mid+1,r,pos,val);
trmx[no] = max(trmx[f1],trmx[f2]);
}
}
int qrmx(int no, int l, int r, int L, int R) {
if(l > R || r < L) return 0;
else if(l >= L && r <= R) return trmx[no];
else {
int f1 = 2*no;
int f2 = 2*no + 1;
int mid = (l+r)>>1;
return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R));
}
}
void attp(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
else if(l == r) trp[no] = val;
else {
int f1 = 2*no;
int f2 = 2*no + 1;
int mid = (l+r)>>1;
attp(f1,l,mid,pos,val);
attp(f2,mid+1,r,pos,val);
trp[no] = (trp[f1]*trp[f2])%mod;
}
}
int qrp(int no, int l, int r, int L, int R) {
if(l > R || r < L) return 1;
else if(l >= L && r <= R) return trp[no];
else {
int f1 = 2*no;
int f2 = 2*no + 1;
int mid = (l+r)>>1;
return (qrp(f1,l,mid,L,R)*qrp(f2,mid+1,r,L,R))%mod;
}
}
int qrr() {
auto it = lr.end(); it--;
dbl logcur = logtot;
int ans = 0;
dbl anslg = 0;
while(true) {
int l = it->fr;
int r = it->sc.fr;
int p = it->sc.sc;
int mx = qrmx(1,0,n-1,l,r);
dbl anscur = log2(mx) + logcur;
if(anscur > anslg) {
anslg = anscur;
ans = (qrp(1,0,n-1,0,r)*mx)%mod;
}
logcur -= log2(p);
if(logcur + logmax < logtot || it == lr.begin()) break;
it--;
}
return ans;
}
int updateX(int pos, int val) {
if(val == a[pos]) {
return qrr();
}
attp(1,0,n-1,pos,val);
logtot-= log2(a[pos]);
logtot+= log2(val);
if(a[pos] != 1 && val != 1) {
a[pos] = val;
return qrr();
}
auto it = lr.upper_bound(pos); it--;
if(val == 1) {
//quero pegar o cara da direita e da esquerda e juntar com esse
vector<int> tir;
int l = pos;
int r = pos;
if(it != lr.begin()) {
it--;
//tiro ele se for igual a 1
if(it->sc.sc == 1) {
l = it->fr;
tir.pb(it->fr);
}
it++;
}
it++;
if(it != lr.end()) {
if(it->sc.sc == 1) {
r = it->sc.fr;
tir.pb(it->fr);
}
}
it--;
tir.pb(it->fr);
for(auto x : tir) {
lr.erase(x);
}
lr[l] = mp(r,1);
}
else {
//quero pegar o cara da direita e da esquerda e separar
int l = it->fr;
int r = it->sc.fr;
lr.erase(l);
if(l != pos) {
//inserir (l,pos-1)
lr[l] = mp(pos-1,1);
}
lr[pos] = mp(pos,val);
if(r != pos) {
lr[pos+1] = mp(r,1);
}
}
a[pos] = val;
return qrr();
}
int updateY(int pos, int val) {
b[pos] = val;
attmx(1,0,n-1,pos,val);
return qrr();
}
int init(int N, int X[], int Y[]() {
n = N;
logtot = 0;
logmax = 31;
for(int i = 0; i < n; i++) {
a[i] = X[i];
logtot+= log2(a[i]);
attp(1,0,n-1,i,a[i]);
}
for(int i = 0; i < n; i++) {
b[i] = Y[i];
attmx(1,0,n-1,i,b[i]);
}
for(int i = 0; i < n;) {
if(a[i] != 1) {
lr[i] = mp(i,a[i]);
i++;
}
else {
int ant = i;
while(i < n && a[i] == 1) {
i++;
}
lr[ant] = mp(i-1,1);
}
}
return qrr();
}