제출 #396806

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
396806	2021-04-30 18:56:30	rainboy	말 (IOI15_horses)	C11	100 / 100	152 ms	30916 KiB

horses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "horses.h"
#include <string.h>
#define N 500000
#define N_  (1 << 19) /* N_ = pow2(ceil(log2(N))) */
#define MD  1000000007
#define INF 0x3f3f3f3f
long long min(long long a, long long b) { return a < b ? a : b; }
int xx[N], yy[N], pp[N_ * 2], qq[N_ * 2], suf_[N_ * 2], prod[N_ * 2], prod_[N_ * 2], n_;
void pul(int i) {
  int l = i << 1, r = l | 1;
  prod[i] = min((long long) prod[l] * prod[r], INF);
  prod_[i] = (long long) prod_[l] * prod_[r] % MD;
  if (pp[r] == 0 || ((long long) pp[l] * qq[r]) / ((long long) qq[l] * pp[r]) >= prod[r])
    pp[i] = pp[l], qq[i] = qq[l] * prod[r], suf_[i] = suf_[l];
  else
    pp[i] = pp[r], qq[i] = qq[r], suf_[i] = (long long) prod_[l] * suf_[r] % MD;
}
int init(int n, int *xx_, int *yy_) {
  int i;
  memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
  n_ = 1;
  while (n_ < n)
    n_ <<= 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

horses.c: In function 'pul':
horses.c:16:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  prod[i] = min((long long) prod[l] * prod[r], INF);
      |            ^~~
horses.c:17:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |  prod_[i] = (long long) prod_[l] * prod_[r] % MD;
      |             ^
horses.c:21:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |   pp[i] = pp[r], qq[i] = qq[r], suf_[i] = (long long) prod_[l] * suf_[r] % MD;
      |                                           ^
horses.c: In function 'init':
horses.c:27:20: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   27 |  memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
      |                    ^
horses.c:27:54: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   27 |  memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
      |                                                      ^
horses.c:33:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |   pp[n_ + i] = i < n ? yy[i] : 0, qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * (i < n ? yy[i] : 0) % MD;
      |                                                                  ^
horses.c: In function 'updateX':
horses.c:42:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  prod[n_ + i] = prod_[n_ + i] = xx[i], suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
      |                                                       ^
horses.c: In function 'updateY':
horses.c:51:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |  pp[n_ + i] = yy[i], qq[n_ + i] = 1, suf_[n_ + i] = (long long) xx[i] * yy[i] % MD;
      |                                                     ^

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