제출 #738980

#제출 시각아이디문제언어결과실행 시간메모리
738980shoryu386말 (IOI15_horses)C++17
54 / 100
1560 ms26076 KiB
#include <bits/stdc++.h> using namespace std; #define MOD 1000000007LL #include "horses.h" //hypothesis 1: There is no point in keeping a partial amount of horses. Sell all, or don't bother. //Let's test this. //Ok, should be confirmed (passed subtask 1) //now, running product of X can be really big //we need to determine the largest value in meow, where meow[i] = Y[i] * prefixProdX[i]; //honestly even Y[i] can be really big (10^9 for both X and Y) //I also don't really want to touch floating point //let our two comparison indices be A and B //without loss of generality, let A < B //then meow[A] = Y[A] * prefixProdX[A], meow[B] = Y[B] * prefixProdX[B] //meow[A] < meow[B] iff //Y[A] * prefixProdX[A] < Y[B] * prefixProdX[B] //Y[A] < Y[B] * prefixProdX[B] / prefixProdX[A] //Y[A] < Y[B] * rangeProdX(A+1, B) //hmm both Y[A] and Y[B] are bounded by 10^9 //meaning if rangeProdX(A+1, B) ever exceeds 10^9, we can safely say meow[B] is greater //Y is also bounded by 1 #define int long long #define actlint int32_t actlint *X, *Y; int N; bool st3 = true; #define MAXN 500001 #define makeMid int mid = (s+e)/2 #define lc(x) (2*x) #define rc(x) (2*x+1) #define parent(x) (x/2) typedef int stdata; stdata ST[4*MAXN+1] = {0}; inline stdata combine(stdata x, stdata y){ return (x*y)%MOD; } void pointSet(int x, stdata y, int index=1, int s=0, int e=N-1){ makeMid; if (s==e){ ST[index] = y; return; } if (x <= mid) pointSet(x, y, lc(index), s, mid); else pointSet(x, y, rc(index), mid+1, e); ST[index] = combine(ST[lc(index)], ST[rc(index)]); } void pointAdd(int x, stdata y, int index=1, int s=0, int e=N-1){ makeMid; if (s==e){ ST[index] += y; return; } if (x <= mid) pointAdd(x, y, lc(index), s, mid); else pointAdd(x, y, rc(index), mid+1, e); ST[index] = combine(ST[lc(index)], ST[rc(index)]); } stdata query(int x, int y, int index=1, int s=0, int e=N-1){ makeMid; if (s==x && e==y) return ST[index]; if (x <= mid && y > mid) return combine(query(x, mid, lc(index), s, mid), query(mid+1, y, rc(index), mid+1, e)); else if (x <= mid) return query(x, y, lc(index), s, mid); else return query(x, y, rc(index), mid+1, e); } int calc(){ //this is bottleneck of code //this takes O(N) time, which is too long since we cannot afford O(NM) //problem that this is meant to solve: //find max of Y[i] * prefixProdX[i] (in log n time?) long long best = 0; long long run = 1; long long init = 0; if (st3) init = max(N-33LL, 0LL), best = max(N-33LL, 0LL); for (int i = init; i < N; i++){ run *= X[i]; if ((int)Y[best] < (int)Y[i] * run){ best = i; run = 1; } } run = query(0, best); run *= Y[best]; run %= MOD; return run; } actlint init(actlint hmN, actlint hmX[], actlint hmY[]) { N = hmN; X = hmX; Y = hmY; for (int i = 0; i < N; i++){ if (X[i] < 2) st3 = false; pointSet(i, X[i]); } return calc(); } actlint updateX(actlint pos, actlint val) { X[pos] = val; if (val < 2) st3 = false; pointSet(pos, val); return calc(); } actlint updateY(actlint pos, actlint val) { Y[pos] = val; return calc(); }

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

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:104:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  104 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:111:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  111 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:116:13: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  116 |  return calc();
      |         ~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...