제출 #364957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364957		BartolM	말 (IOI15_horses)	C++17	0 / 100	1579 ms	20648 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int OFF=(1<<19);
const int MAXN=5e5+5;

int n;
pii T[2*OFF];
int Tmax[2*OFF];
int x[MAXN], y[MAXN];

int mul(int a, int b) {
    return (ll)a*b%MOD;
}

pii mrg(pii a, pii b) {
    pii ret=mp(mul(a.X, b.X), a.Y || b.Y);
    ret.Y|=((ll)ret.X!=(ll)a.X*b.X);
    return ret;
}

int nadji(int val, int pos=1) {
    ll curr=1; int ind=n-1;
    while (ind>=0) {
        curr*=x[ind];
        if (curr>=val) return ind;
        ind--;
    }
    return -1;
//    if (pos>=OFF) return pos-OFF;
//    if (T[pos*2+1].Y || (!T[pos*2+1].Y && T[pos*2+1].X>=val)) return nadji(val, pos*2+1);
//    return nadji(val/T[pos*2+1].X+!!(val%T[pos*2+1].X), pos*2);
}

int query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return T[pos].X;
    if (lo>=b || hi<=a) return 1;
    int mid=(lo+hi)/2;
    return mul(query(a, b, pos*2, lo, mid), query(a, b, pos*2+1, mid, hi));
}

int answer() {
    int res=-1; double maxi=1, curr=1;
    for (int i=0; i<n; ++i) {
        curr*=x[i];
        if (curr*y[i]>maxi) res=i, maxi=curr*y[i];
    }
    int ret=1;
    for (int i=0; i<=res; ++i) ret=mul(ret, x[i]);
    return mul(ret, y[res]);
}

int init(int N, int XX[], int YY[]) {
    n=N;
    for (int i=0; i<n; ++i) x[i]=XX[i], y[i]=YY[i];

    fill(T, T+2*OFF, mp(1, 0));
    memset(Tmax, 0, sizeof Tmax);
    for (int i=0; i<n; ++i) T[OFF+i].X=x[i], Tmax[OFF+i]=y[i];
    for (int i=OFF-1; i>0; --i) T[i]=mrg(T[i*2], T[i*2+1]), Tmax[i]=max(Tmax[i*2], Tmax[i*2+1]);

    return answer();
}

int updateX(int pos, int val) {
    x[pos]=val;
    pos+=OFF;
    T[pos].X=val;
    pos/=2;
    while (pos) {
        T[pos]=mrg(T[pos*2], T[pos*2+1]);
        pos/=2;
    }
    return answer();
}

int updateY(int pos, int val) {
    y[pos]=val;
    pos+=OFF;
    Tmax[pos]=val;
    pos/=2;
    while (pos) {
        Tmax[pos]=max(Tmax[pos*2], Tmax[pos*2+1]);
        pos/=2;
    }
    return answer();
}

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

horses.cpp: In function 'int mul(int, int)':
horses.cpp:27:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |     return (ll)a*b%MOD;
      |            ~~~~~~~^~~~
horses.cpp: In function 'int nadji(int, int)':
horses.cpp:36:24: warning: unused parameter 'pos' [-Wunused-parameter]
   36 | int nadji(int val, int pos=1) {
      |                    ~~~~^~~~~

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