| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 523614 | Lobo | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
#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
long long n, a[maxn], b[maxn], trmx[4*maxn], trp[4*maxn];
map<long long,pair<long long,long long>> lr;
long long mod = 1e9 + 7;
dbl logmax, logtot;
void attmx(long long no, long long l, long long r, long long pos, long long val) {
if(l > pos || r < pos) return;
else if(l == r) trmx[no] = val;
else {
long long f1 = 2*no;
long long f2 = 2*no + 1;
long long mid = (l+r)>>1;
attmx(f1,l,mid,pos,val);
attmx(f2,mid+1,r,pos,val);
trmx[no] = max(trmx[f1],trmx[f2]);
}
}
long long qrmx(long long no, long long l, long long r, long long L, long long R) {
if(l > R || r < L) return 0;
else if(l >= L && r <= R) return trmx[no];
else {
long long f1 = 2*no;
long long f2 = 2*no + 1;
long long mid = (l+r)>>1;
return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R));
}
}
void attp(long long no, long long l, long long r, long long pos, long long val) {
if(l > pos || r < pos) return;
else if(l == r) trp[no] = val;
else {
long long f1 = 2*no;
long long f2 = 2*no + 1;
long long mid = (l+r)>>1;
attp(f1,l,mid,pos,val);
attp(f2,mid+1,r,pos,val);
trp[no] = (trp[f1]*trp[f2])%mod;
}
}
long long qrp(long long no, long long l, long long r, long long L, long long R) {
if(l > R || r < L) return 1;
else if(l >= L && r <= R) return trp[no];
else {
long long f1 = 2*no;
long long f2 = 2*no + 1;
long long mid = (l+r)>>1;
return (qrp(f1,l,mid,L,R)*qrp(f2,mid+1,r,L,R))%mod;
}
}
long long qrr() {
auto it = lr.end(); it--;
dbl logcur = logtot;
long long ans = 0;
dbl anslg = 0;
while(true) {
long long l = it->fr;
long long r = it->sc.fr;
long long p = it->sc.sc;
long long 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;
}
long long init(long long N, long long X[], long long Y[]) {
n = N;
logtot = 0;
logmax = 31;
for(long long i = 0; i < n; i++) {
a[i] = X[i];
logtot+= log2(a[i]);
attp(1,0,n-1,i,a[i]);
}
for(long long i = 0; i < n; i++) {
b[i] = Y[i];
attmx(1,0,n-1,i,b[i]);
}
for(long long i = 0; i < n;) {
if(a[i] != 1) {
lr[i] = mp(i,a[i]);
i++;
}
else {
long long ant = i;
while(i < n && a[i] == 1) {
i++;
}
lr[ant] = mp(i-1,1);
}
}
return qrr();
}
long long updateX(long long pos, long long 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<long long> tir;
long long l = pos;
long long 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
long long l = it->fr;
long long 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();
}
long long updateY(long long pos, long long val) {
b[pos] = val;
attmx(1,0,n-1,pos,val);
return qrr();
}