제출 #320397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320397		neki	Horses (IOI15_horses)	C++14	17 / 100	533 ms	102136 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long 
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn (1<<19)
#define pa pair<ll, ll>
#define ld long double 
#define mod 1000000007
ll l[2* mn], r[2 * mn], m[2 * mn], x[mn], y[mn], n, tmod[2 * mn];
pair<ld, ll> tlog[2* mn];
ld up[2 * mn];
pair<ld, ll> max(pair<ld, ll> a, pair<ld, ll> b){
    if(a.fi>b.fi) return a;
    else{ return b;}
}
ll pot(ll ex, ll bas){
    ll ret=1;
    while(ex){
        if(ex&1)ret*=bas, ret%=mod;
        ex/=2;
        bas*=bas;bas%=mod;
    }
    return ret;
}
pair<ld, ll> mlog(ll tl, ll tr, ld v=0, ll no=1){
    if(tl>=tr) return make_pair(-1.0, -1);
    if(tl==l[no] && tr==r[no]){
        up[no]+=v;
        auto ret=tlog[no];ret.fi+=up[no];
        return ret;
    }
    auto ret=max(mlog(tl, min(m[no], tr), v, no *2), mlog(max(m[no], tl),tr, v, no *2 +1));
    ret.fi+=up[no];
    auto a=tlog[no*2];a.fi+=up[no *2];auto b=tlog[no*2+1];b.fi+=up[no *2+1];
    tlog[no]=max(a, b);
    return ret;
}
void upd(ll p, ll val){for(p+=mn;p>0;p>>=1) tmod[p]*=val, tmod[p]%=mod;}
ll que(ll ql, ll qr){
    ll ret=1;
    for(ql+=mn, qr+=mn;ql<qr;ql>>=1, qr>>=1){
        if(ql&1) ret*=tmod[ql++], ret%=mod;
        if(qr&1) ret*=tmod[--qr], ret%=mod;
    }
    return ret;
}

int init(int N, int X[], int Y[]){
    n=N;
    loop(i, 0, 2 * mn)tmod[i]=1;
    loop(i, 0, n) x[i]=X[i], y[i]=Y[i], tmod[i+mn]=x[i];
    loop(i, 0, mn) l[i+mn]=i, r[i+mn]=i+1;
    pool(i, mn, 1) l[i]=l[i*2], r[i]=r[i*2+1], m[i]=r[i*2];
    
    ld cur=0.0;
    loop(i, 0, n) cur+=log(x[i]), tlog[i+mn].fi=cur+log(y[i]), tlog[i+mn].se=i;
    pool(i, mn, 1) tlog[i]=max(tlog[i * 2], tlog[i * 2 + 1]), tmod[i]=(tmod[i *2] * tmod[i * 2 +1])%mod;
    
    ll ans=mlog(0, n).se;
    ll ret=que(0, ans+1);
    ret*=y[ans];ret%=mod;
    return ret;
}
int updateX(int pos, int val){
    upd(pos, (val * pot(x[pos], mod-2))%mod);
    mlog(pos, n, log(val)-log(x[pos]));
    
    x[pos]=val;
    
    ll ans=mlog(0, n).se;
    ll ret=que(0, ans+1);
    ret*=y[ans];ret%=mod;
    return ret;
}
int updateY(int pos, int val){
    mlog(pos, pos+1, log(val)-log(y[pos]));
    
    y[pos]=val;
    
    ll ans=mlog(0, n).se;
    ll ret=que(0, ans+1);
    ret*=y[ans];ret%=mod;
    return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |     return ret;
      |            ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |     return ret;
      |            ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |     return ret;
      |            ^~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23