답안 #65647 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65647	2018-08-08T10:12:52 Z	mirbek01	말 (IOI15_horses)	C++17	100 / 100	267 ms	276984 KB

horses

#include "horses.h"

# include <bits/stdc++.h>

using namespace std;

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

int n, X[N], Y[N];

double x[N], y[N];

struct node{
      double sum, pref;
      long long res, pr;
};

node t[N * 4];

inline node combine (node a, node b)
{
      node c;
      c.sum = a.sum + b.sum;
      c.res = a.res * b.res % mod;
      if (a.pref > a.sum + b.pref)
      {
            c.pref = a.pref;
            c.pr = a.pr;
      }
      else
      {
            c.pref = a.sum + b.pref;
            c.pr = a.res * b.pr % mod;
      }
      return c;
}

void build(int v = 1, int tl = 0, int tr = n - 1){
      if (tl == tr)
      {
            t[v].sum = x[tl];
            t[v].pref = x[tl] + y[tl];
            t[v].res = X[tl];
            t[v].pr = X[tl] * 1ll * Y[tl] % mod;
      }
      else
      {
            int tm = (tl + tr) >> 1;
            build( v + v, tl, tm );
            build( v + v + 1, tm + 1, tr );

            t[v] = combine( t[v + v], t[v + v + 1] );
      }
}

int init(int NN, int a[], int b[]) {
      n = NN;
      for(int i = 0; i < n; i ++)
            x[i] = log10(a[i]), y[i] = log10(b[i]), X[i] = a[i], Y[i] = b[i];
      build();

      return t[1].pr;
}

void update (int pos, int val, int v = 1, int tl = 0, int tr = n - 1)
{
      if (tl == tr)
      {
            t[v].sum = x[tl];
            t[v].pref = x[tl] + y[tl];
            t[v].res = X[tl];
            t[v].pr = X[tl] * 1ll * Y[tl] % mod;
      }
      else
      {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                  update( pos, val, v + v, tl, tm );
            else
                  update( pos, val, v + v + 1, tm + 1, tr );

            t[v] = combine( t[v + v], t[v + v + 1] );
      }
}

int updateX(int pos, int val) {
      X[pos] = val;
      x[pos] = log10(val);
      update( pos, val );

      return t[1].pr;
}

int updateY(int pos, int val) {
      Y[pos] = val;
      y[pos] = log10(val);
      update( pos, val );

      return t[1].pr;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:63:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:92:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:100:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
       return t[1].pr;
              ~~~~~^~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	432 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	556 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Correct	2 ms	652 KB	Output is correct
8	Correct	2 ms	652 KB	Output is correct
9	Correct	3 ms	728 KB	Output is correct
10	Correct	2 ms	728 KB	Output is correct
11	Correct	2 ms	728 KB	Output is correct
12	Correct	3 ms	732 KB	Output is correct
13	Correct	2 ms	732 KB	Output is correct
14	Correct	4 ms	732 KB	Output is correct
15	Correct	2 ms	732 KB	Output is correct
16	Correct	3 ms	732 KB	Output is correct
17	Correct	2 ms	732 KB	Output is correct
18	Correct	2 ms	732 KB	Output is correct
19	Correct	2 ms	732 KB	Output is correct
20	Correct	3 ms	732 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	732 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	2 ms	732 KB	Output is correct
4	Correct	2 ms	732 KB	Output is correct
5	Correct	2 ms	732 KB	Output is correct
6	Correct	4 ms	732 KB	Output is correct
7	Correct	2 ms	732 KB	Output is correct
8	Correct	2 ms	732 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	3 ms	732 KB	Output is correct
11	Correct	3 ms	732 KB	Output is correct
12	Correct	2 ms	732 KB	Output is correct
13	Correct	2 ms	732 KB	Output is correct
14	Correct	2 ms	732 KB	Output is correct
15	Correct	2 ms	732 KB	Output is correct
16	Correct	2 ms	732 KB	Output is correct
17	Correct	2 ms	732 KB	Output is correct
18	Correct	2 ms	732 KB	Output is correct
19	Correct	2 ms	732 KB	Output is correct
20	Correct	2 ms	732 KB	Output is correct
21	Correct	2 ms	732 KB	Output is correct
22	Correct	2 ms	732 KB	Output is correct
23	Correct	3 ms	764 KB	Output is correct
24	Correct	3 ms	764 KB	Output is correct
25	Correct	3 ms	780 KB	Output is correct
26	Correct	2 ms	796 KB	Output is correct
27	Correct	2 ms	916 KB	Output is correct
28	Correct	3 ms	916 KB	Output is correct
29	Correct	2 ms	916 KB	Output is correct
30	Correct	3 ms	916 KB	Output is correct
31	Correct	3 ms	916 KB	Output is correct
32	Correct	3 ms	916 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	50048 KB	Output is correct
2	Correct	239 ms	62636 KB	Output is correct
3	Correct	181 ms	66660 KB	Output is correct
4	Correct	215 ms	74172 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	74172 KB	Output is correct
2	Correct	2 ms	74172 KB	Output is correct
3	Correct	3 ms	74172 KB	Output is correct
4	Correct	2 ms	74172 KB	Output is correct
5	Correct	2 ms	74172 KB	Output is correct
6	Correct	2 ms	74172 KB	Output is correct
7	Correct	2 ms	74172 KB	Output is correct
8	Correct	2 ms	74172 KB	Output is correct
9	Correct	2 ms	74172 KB	Output is correct
10	Correct	2 ms	74172 KB	Output is correct
11	Correct	2 ms	74172 KB	Output is correct
12	Correct	3 ms	74172 KB	Output is correct
13	Correct	3 ms	74172 KB	Output is correct
14	Correct	2 ms	74172 KB	Output is correct
15	Correct	2 ms	74172 KB	Output is correct
16	Correct	2 ms	74172 KB	Output is correct
17	Correct	2 ms	74172 KB	Output is correct
18	Correct	3 ms	74172 KB	Output is correct
19	Correct	3 ms	74172 KB	Output is correct
20	Correct	2 ms	74172 KB	Output is correct
21	Correct	2 ms	74172 KB	Output is correct
22	Correct	3 ms	74172 KB	Output is correct
23	Correct	3 ms	74172 KB	Output is correct
24	Correct	3 ms	74172 KB	Output is correct
25	Correct	3 ms	74172 KB	Output is correct
26	Correct	2 ms	74172 KB	Output is correct
27	Correct	2 ms	74172 KB	Output is correct
28	Correct	2 ms	74172 KB	Output is correct
29	Correct	3 ms	74172 KB	Output is correct
30	Correct	3 ms	74172 KB	Output is correct
31	Correct	4 ms	74172 KB	Output is correct
32	Correct	3 ms	74172 KB	Output is correct
33	Correct	103 ms	74172 KB	Output is correct
34	Correct	113 ms	77340 KB	Output is correct
35	Correct	161 ms	88184 KB	Output is correct
36	Correct	137 ms	98920 KB	Output is correct
37	Correct	72 ms	101060 KB	Output is correct
38	Correct	104 ms	104036 KB	Output is correct
39	Correct	68 ms	106100 KB	Output is correct
40	Correct	94 ms	111932 KB	Output is correct
41	Correct	65 ms	113996 KB	Output is correct
42	Correct	65 ms	116084 KB	Output is correct
43	Correct	104 ms	122360 KB	Output is correct
44	Correct	108 ms	128744 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	128744 KB	Output is correct
2	Correct	2 ms	128744 KB	Output is correct
3	Correct	2 ms	128744 KB	Output is correct
4	Correct	2 ms	128744 KB	Output is correct
5	Correct	2 ms	128744 KB	Output is correct
6	Correct	2 ms	128744 KB	Output is correct
7	Correct	2 ms	128744 KB	Output is correct
8	Correct	2 ms	128744 KB	Output is correct
9	Correct	3 ms	128744 KB	Output is correct
10	Correct	2 ms	128744 KB	Output is correct
11	Correct	3 ms	128744 KB	Output is correct
12	Correct	3 ms	128744 KB	Output is correct
13	Correct	3 ms	128744 KB	Output is correct
14	Correct	2 ms	128744 KB	Output is correct
15	Correct	2 ms	128744 KB	Output is correct
16	Correct	3 ms	128744 KB	Output is correct
17	Correct	2 ms	128744 KB	Output is correct
18	Correct	2 ms	128744 KB	Output is correct
19	Correct	2 ms	128744 KB	Output is correct
20	Correct	3 ms	128744 KB	Output is correct
21	Correct	2 ms	128744 KB	Output is correct
22	Correct	2 ms	128744 KB	Output is correct
23	Correct	3 ms	128744 KB	Output is correct
24	Correct	3 ms	128744 KB	Output is correct
25	Correct	3 ms	128744 KB	Output is correct
26	Correct	4 ms	128744 KB	Output is correct
27	Correct	3 ms	128744 KB	Output is correct
28	Correct	3 ms	128744 KB	Output is correct
29	Correct	4 ms	128744 KB	Output is correct
30	Correct	3 ms	128744 KB	Output is correct
31	Correct	4 ms	128744 KB	Output is correct
32	Correct	3 ms	128744 KB	Output is correct
33	Correct	113 ms	131360 KB	Output is correct
34	Correct	252 ms	144072 KB	Output is correct
35	Correct	213 ms	147844 KB	Output is correct
36	Correct	267 ms	155528 KB	Output is correct
37	Correct	103 ms	158516 KB	Output is correct
38	Correct	97 ms	162440 KB	Output is correct
39	Correct	138 ms	173292 KB	Output is correct
40	Correct	135 ms	184176 KB	Output is correct
41	Correct	87 ms	186232 KB	Output is correct
42	Correct	97 ms	189284 KB	Output is correct
43	Correct	70 ms	191204 KB	Output is correct
44	Correct	112 ms	197312 KB	Output is correct
45	Correct	79 ms	199436 KB	Output is correct
46	Correct	66 ms	201436 KB	Output is correct
47	Correct	100 ms	207728 KB	Output is correct
48	Correct	110 ms	214120 KB	Output is correct
49	Correct	211 ms	220000 KB	Output is correct
50	Correct	222 ms	225184 KB	Output is correct
51	Correct	225 ms	236932 KB	Output is correct
52	Correct	178 ms	248320 KB	Output is correct
53	Correct	215 ms	251916 KB	Output is correct
54	Correct	145 ms	255660 KB	Output is correct
55	Correct	98 ms	257924 KB	Output is correct
56	Correct	159 ms	265464 KB	Output is correct
57	Correct	125 ms	268332 KB	Output is correct
58	Correct	114 ms	271632 KB	Output is correct
59	Correct	91 ms	276984 KB	Output is correct

답안 #65647

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0