제출 #225534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
225534		nickmet2004	말 (IOI15_horses)	C++11	0 / 100	774 ms	36272 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e5 + 5 , mod = 1e9 + 7;

int n;
vector<int> x , y;
int xmult;
set<int> poss;
int T[1 << 20];

int pow(int a , int p){
    int res = 0; a %= mod;
    while(p){
        if(p & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        p /= 2;
    }return res;
}
inline int Inv(int a) {return pow(a % mod, mod - 2);}

void upd(int idx , int v , int l = 0 , int r = n - 1 , int pos = 0){
    if(l == r){
        T[pos] = v;return;
    }
    int mid = (l + r) >> 1;
    if(l <= idx && idx <= mid) upd(idx , v , l , mid , pos * 2 + 1);
    if(mid < idx && idx <= r) upd(idx , v , mid + 1 , r , pos * 2 + 2);
    T[pos] = max(T[pos + pos + 1] , T[pos + pos + 2]);
}
int get(int L , int R , int l = 0 , int r= n - 1 , int pos = 0){
    if(r < L || R < l) return INT_MIN;
    if(L <= l && r <= R) return T[pos];
    int mid = (l + r) >> 1;
    return max(get(L , R , l , mid , pos * 2 + 1) , get(L , R , mid + 1 , r , pos * 2 + 2));
}
struct div{
    ll a , b;
    bool operator<(const div &A) const {
         return a * A.b < b * A.a;
    }
}mx;

int solve(){
    mx.a = 0 ; mx.b = 1;
    ll curxmult = 1;
    /// (y / curxmult) has to be as large as possible
    for(auto it = poss.rbegin(); it != poss.rend() && curxmult < 1000000000; ++it){
        int i = *it;
        int j = (it == poss.rbegin()) ? n : *prev(it);
        mx = max(mx , {get(i , j - 1) , curxmult});
        curxmult *= x[i];
    }
    int res = (mx.a * Inv(mx.b)) % mod;
    return res = (res * xmult) % mod;
}

int init(int N , int X[] , int Y[]){
    n = N;
    x.assign(X , X + N);
    y.assign(Y , Y + N);
    for(int i = 0; i < n; ++i){
        upd(i , y[i]);
    }
    xmult = 1;
    poss.insert(0);
    for(int i = 0; i < n; ++i){
        if(x[i] > 1){
            poss.insert(i);
            xmult = (xmult * x[i]) % mod;
        }
    }
    return solve();
}
int updateX(int pos , int val){
    if(x[pos] > 1 && val == 1) poss.erase(pos);
    if(x[pos] == 1 && val > 1) poss.insert(pos);
    xmult = (xmult * Inv(x[pos])) % mod;
    xmult = (xmult * (x[pos] = val)) % mod;
    return solve();
}
int updateY(int pos , int val){
    upd(pos , y[pos] = val);
    return solve();
}
///int main (){}

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

horses.cpp: In function 'int solve()':
horses.cpp:56:30: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int res = (mx.a * Inv(mx.b)) % mod;
                           ~~~^
horses.cpp:56:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     int res = (mx.a * Inv(mx.b)) % mod;
               ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:60:35: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N , int X[] , int Y[]){
                                   ^
horses.cpp:6:11: note: shadowed declaration is here
 const int N = 5e5 + 5 , mod = 1e9 + 7;
           ^

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