oj.uz

Submission #126501

# Submission time Handle Problem Language Result Execution time Memory
126501 2019-07-08T01:36:12 Z dragonslayerit Horses (IOI15_horses) C++14
100 / 100
 406 ms 53052 KB 
#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;
}

Compilation message

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 26 ms 31608 KB Output is correct
4 Correct 26 ms 31608 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 33 ms 31608 KB Output is correct
7 Correct 26 ms 31608 KB Output is correct
8 Correct 26 ms 31608 KB Output is correct
9 Correct 27 ms 31612 KB Output is correct
10 Correct 27 ms 31608 KB Output is correct
11 Correct 26 ms 31608 KB Output is correct
12 Correct 27 ms 31608 KB Output is correct
13 Correct 26 ms 31608 KB Output is correct
14 Correct 27 ms 31736 KB Output is correct
15 Correct 26 ms 31608 KB Output is correct
16 Correct 27 ms 31608 KB Output is correct
17 Correct 26 ms 31608 KB Output is correct
18 Correct 27 ms 31608 KB Output is correct
19 Correct 27 ms 31608 KB Output is correct
20 Correct 31 ms 31580 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31612 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 27 ms 31608 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 29 ms 31608 KB Output is correct
6 Correct 26 ms 31608 KB Output is correct
7 Correct 27 ms 31652 KB Output is correct
8 Correct 26 ms 31608 KB Output is correct
9 Correct 26 ms 31608 KB Output is correct
10 Correct 26 ms 31608 KB Output is correct
11 Correct 31 ms 31608 KB Output is correct
12 Correct 28 ms 31576 KB Output is correct
13 Correct 32 ms 31704 KB Output is correct
14 Correct 32 ms 31608 KB Output is correct
15 Correct 31 ms 31608 KB Output is correct
16 Correct 31 ms 31608 KB Output is correct
17 Correct 26 ms 31608 KB Output is correct
18 Correct 27 ms 31736 KB Output is correct
19 Correct 26 ms 31608 KB Output is correct
20 Correct 26 ms 31580 KB Output is correct
21 Correct 26 ms 31608 KB Output is correct
22 Correct 27 ms 31608 KB Output is correct
23 Correct 27 ms 31736 KB Output is correct
24 Correct 27 ms 31736 KB Output is correct
25 Correct 27 ms 31608 KB Output is correct
26 Correct 27 ms 31612 KB Output is correct
27 Correct 28 ms 31736 KB Output is correct
28 Correct 27 ms 31736 KB Output is correct
29 Correct 27 ms 31608 KB Output is correct
30 Correct 27 ms 31736 KB Output is correct
31 Correct 27 ms 31736 KB Output is correct
32 Correct 27 ms 31632 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 44328 KB Output is correct
2 Correct 406 ms 53052 KB Output is correct
3 Correct 347 ms 44328 KB Output is correct
4 Correct 366 ms 48220 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31612 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 26 ms 31608 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 26 ms 31560 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31608 KB Output is correct
10 Correct 26 ms 31608 KB Output is correct
11 Correct 26 ms 31608 KB Output is correct
12 Correct 27 ms 31608 KB Output is correct
13 Correct 27 ms 31608 KB Output is correct
14 Correct 26 ms 31608 KB Output is correct
15 Correct 26 ms 31608 KB Output is correct
16 Correct 26 ms 31608 KB Output is correct
17 Correct 27 ms 31608 KB Output is correct
18 Correct 26 ms 31608 KB Output is correct
19 Correct 26 ms 31608 KB Output is correct
20 Correct 27 ms 31608 KB Output is correct
21 Correct 29 ms 31608 KB Output is correct
22 Correct 26 ms 31608 KB Output is correct
23 Correct 28 ms 31608 KB Output is correct
24 Correct 28 ms 31740 KB Output is correct
25 Correct 27 ms 31736 KB Output is correct
26 Correct 27 ms 31736 KB Output is correct
27 Correct 27 ms 31736 KB Output is correct
28 Correct 27 ms 31608 KB Output is correct
29 Correct 27 ms 31608 KB Output is correct
30 Correct 27 ms 31608 KB Output is correct
31 Correct 27 ms 31736 KB Output is correct
32 Correct 32 ms 31736 KB Output is correct
33 Correct 210 ms 43512 KB Output is correct
34 Correct 214 ms 43456 KB Output is correct
35 Correct 277 ms 50396 KB Output is correct
36 Correct 276 ms 50296 KB Output is correct
37 Correct 179 ms 41720 KB Output is correct
38 Correct 239 ms 42524 KB Output is correct
39 Correct 175 ms 41592 KB Output is correct
40 Correct 247 ms 45508 KB Output is correct
41 Correct 173 ms 41592 KB Output is correct
42 Correct 176 ms 41636 KB Output is correct
43 Correct 244 ms 45948 KB Output is correct
44 Correct 245 ms 45816 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 26 ms 31612 KB Output is correct
3 Correct 27 ms 31736 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 26 ms 31608 KB Output is correct
6 Correct 27 ms 31736 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Correct 26 ms 31608 KB Output is correct
9 Correct 26 ms 31608 KB Output is correct
10 Correct 27 ms 31608 KB Output is correct
11 Correct 27 ms 31608 KB Output is correct
12 Correct 26 ms 31612 KB Output is correct
13 Correct 26 ms 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 26 ms 31608 KB Output is correct
16 Correct 27 ms 31580 KB Output is correct
17 Correct 26 ms 31608 KB Output is correct
18 Correct 26 ms 31608 KB Output is correct
19 Correct 26 ms 31608 KB Output is correct
20 Correct 26 ms 31608 KB Output is correct
21 Correct 26 ms 31608 KB Output is correct
22 Correct 26 ms 31608 KB Output is correct
23 Correct 28 ms 31736 KB Output is correct
24 Correct 28 ms 31736 KB Output is correct
25 Correct 27 ms 31736 KB Output is correct
26 Correct 27 ms 31736 KB Output is correct
27 Correct 27 ms 31736 KB Output is correct
28 Correct 32 ms 31736 KB Output is correct
29 Correct 27 ms 31736 KB Output is correct
30 Correct 27 ms 31736 KB Output is correct
31 Correct 27 ms 31636 KB Output is correct
32 Correct 32 ms 31608 KB Output is correct
33 Correct 307 ms 44252 KB Output is correct
34 Correct 390 ms 52960 KB Output is correct
35 Correct 334 ms 44280 KB Output is correct
36 Correct 359 ms 48248 KB Output is correct
37 Correct 210 ms 43512 KB Output is correct
38 Correct 208 ms 43484 KB Output is correct
39 Correct 276 ms 50424 KB Output is correct
40 Correct 275 ms 50424 KB Output is correct
41 Correct 179 ms 41720 KB Output is correct
42 Correct 240 ms 42616 KB Output is correct
43 Correct 173 ms 41588 KB Output is correct
44 Correct 247 ms 45432 KB Output is correct
45 Correct 175 ms 41592 KB Output is correct
46 Correct 177 ms 41756 KB Output is correct
47 Correct 244 ms 45816 KB Output is correct
48 Correct 244 ms 45816 KB Output is correct
49 Correct 306 ms 45560 KB Output is correct
50 Correct 300 ms 45560 KB Output is correct
51 Correct 332 ms 52344 KB Output is correct
52 Correct 327 ms 51832 KB Output is correct
53 Correct 274 ms 43896 KB Output is correct
54 Correct 297 ms 44384 KB Output is correct
55 Correct 221 ms 42616 KB Output is correct
56 Correct 298 ms 47352 KB Output is correct
57 Correct 220 ms 43256 KB Output is correct
58 Correct 228 ms 43768 KB Output is correct
59 Correct 244 ms 46072 KB Output is correct