제출 #126501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126501		dragonslayerit	말 (IOI15_horses)	C++14	100 / 100	406 ms	53052 KiB

horses

#include "horses.h"
#include <algorithm>
#include <cmath>
#include <cstdio>

const int MOD=1e9+7;

struct Number{
  int rem;
  double lg;
  Number(int x):rem(x),lg(std::log(x)){
  }
  Number(int rem,double lg):rem(rem),lg(lg){
  }
  Number operator*(Number num)const{
    return Number(1LL*rem*num.rem%MOD,lg+num.lg);
  }
  bool operator<(Number num)const{
    return lg<num.lg;
  }
};

struct Node{
  Number mult,sell;
  Node():mult(1),sell(1){
  }
  Node(Number mult,Number sell):mult(mult),sell(sell){
  }
}st[1000000];
int xs[1000000];
int ys[1000000];
int N;

Node combine(Node a,Node b){
  return Node(a.mult*b.mult,std::max(a.sell,a.mult*b.sell));
}

void pull(int i){
  st[i]=combine(st[i<<1],st[i<<1|1]);
}

void recalc(int i){
  st[i+N]=Node(Number(xs[i]),Number(xs[i])*Number(ys[i]));
  for(i+=N;i>1;i>>=1){
    pull(i>>1);
  }
}

Node query(int a,int b){
  Node lsum,rsum;
  for(a+=N,b+=N;a<b;a>>=1,b>>=1){
    if(a&1) lsum=combine(lsum,st[a++]);
    if(b&1) rsum=combine(st[--b],rsum);
  }
  return combine(lsum,rsum);
}

/*
void dump(){
  for(int i=0;i<N*2;i++){
    printf("(%d,%d)",st[i].mult.rem,st[i].sell.rem);
  }
  Node res=query(0,N);
  printf(":(%d,%d)\n",res.mult.rem,res.sell.rem);
}
*/

int init(int N, int X[], int Y[]) {
  ::N=N;
  std::copy(X,X+N,xs);
  std::copy(Y,Y+N,ys);
  for(int i=0;i<N;i++){
    recalc(i);
  }
  //dump();
  return query(0,N).sell.rem;
}

int updateX(int pos, int val) {
  xs[pos]=val;
  recalc(pos);
  //dump();
  return query(0,N).sell.rem;
}

int updateY(int pos, int val) {
  ys[pos]=val;
  recalc(pos);
  //dump();
  return query(0,N).sell.rem;
}

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

horses.cpp: In constructor 'Number::Number(int, double)':
horses.cpp:13:28: warning: declaration of 'lg' shadows a member of 'Number' [-Wshadow]
   Number(int rem,double lg):rem(rem),lg(lg){
                            ^
horses.cpp:10:10: note: shadowed declaration is here
   double lg;
          ^~
horses.cpp:13:28: warning: declaration of 'rem' shadows a member of 'Number' [-Wshadow]
   Number(int rem,double lg):rem(rem),lg(lg){
                            ^
horses.cpp:9:7: note: shadowed declaration is here
   int rem;
       ^~~
horses.cpp: In member function 'Number Number::operator*(Number) const':
horses.cpp:16:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return Number(1LL*rem*num.rem%MOD,lg+num.lg);
                   ~~~~~~~~~~~~~~~^~~~
horses.cpp: In constructor 'Node::Node(Number, Number)':
horses.cpp:27:32: warning: declaration of 'sell' shadows a member of 'Node' [-Wshadow]
   Node(Number mult,Number sell):mult(mult),sell(sell){
                                ^
horses.cpp:24:15: note: shadowed declaration is here
   Number mult,sell;
               ^~~~
horses.cpp:27:32: warning: declaration of 'mult' shadows a member of 'Node' [-Wshadow]
   Node(Number mult,Number sell):mult(mult),sell(sell){
                                ^
horses.cpp:24:10: note: shadowed declaration is here
   Number mult,sell;
          ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:68:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:32:5: note: shadowed declaration is here
 int N;
     ^

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