oj.uz

Submission #169904

# Submission time Handle Problem Language Result Execution time Memory
169904 2019-12-23T08:46:09 Z AlexLuchianov Horses (IOI15_horses) C++14
100 / 100
 928 ms 146292 KB 
#include "horses.h"
#include <cmath>
#include <vector>
#include <iostream>

using ll = long long;
using ld = long double;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
int const modulo = 1000000007;

void gcd(int a, int b, int &x, int &y){
  if(b == 0){
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, x, y);
    int aux = x;
    x = y;
    y = aux - a / b * y;
  }
}

struct Number{
  ld lg;
  int val;
  Number(int val = 1){
    lg = log(val);
    this->val = val % modulo;
  }
  Number operator * (Number const &a) const{
    Number result;
    result.lg = lg + a.lg;
    result.val = 1LL * val * a.val % modulo;
    return result;
  }
  Number operator / (Number const &a) const{
    Number result;
    result.lg = lg - a.lg;
    int x, y;
    gcd(a.val, modulo, x, y);
    x = x % modulo;
    if(x < 0)
      x += modulo;
    result.val = 1LL * val * x % modulo;
    return result;
  }
  bool operator < (Number const &a) const{
    return lg < a.lg;
  }
};

class SegmentTree{
private:
  std::vector<Number> aint;
  std::vector<Number> lazy;
public:
  SegmentTree(int n = 0){
    aint.resize(4 * n);
    lazy.resize(4 * n);
  }
  void cleannode(int node, int from, int to){
    if(lazy[node].val == 1)
      return ;

    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] = lazy[node * 2] * lazy[node];
      lazy[node * 2 + 1] = lazy[node * 2 + 1] * lazy[node];
    }
    aint[node] = aint[node] * lazy[node];
    lazy[node] = 1;
  }
  void computenode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      if(aint[node * 2] < aint[node * 2 + 1])
        aint[node] = aint[node * 2 + 1];
      else
        aint[node] = aint[node * 2];
    }
  }
  void update(int node, int from, int to, int x, int y, Number val){
    if(from == x && to == y){
      lazy[node] = lazy[node] * val;
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(mid, y), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }
  Number query(int node, int from, int to, int x, int y){
    cleannode(node, from, to);
    if(from == x && to == y){
      return aint[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else{
        Number result = query(node * 2, from, mid, x, mid);
        Number result2 = query(node * 2 + 1, mid + 1, to, mid + 1, y);
        if(result < result2)
          return result2;
        else
          return result;
      }
    }
  }
};

SegmentTree aint;
int n;
int X[1 + nmax];
int Y[1 + nmax];

int init(int N_, int X_[], int Y_[]) {
  n = N_;
  aint = SegmentTree(n);

  for(int i = 0; i < n; i++)
    X[i] = X_[i];
  for(int i = 0; i < n; i++)
    Y[i] = Y_[i];

  for(int i = 0; i < n; i++)
    aint.update(1, 0, n - 1, i, n - 1, X[i]);

  for(int i = 0; i < n; i++)
    aint.update(1, 0, n - 1, i, i, Y[i]);

	return aint.query(1, 0, n - 1, 0, n - 1).val;
}

int updateX(int pos, int val) {
  aint.update(1, 0, n - 1, pos, n - 1, Number(val) / Number(X[pos]));
  X[pos] = val;
	return aint.query(1, 0, n - 1, 0, n - 1).val;
}

int updateY(int pos, int val) {
  aint.update(1, 0, n - 1, pos, pos, Number(val) / Number(Y[pos]));
  Y[pos] = val;
	return aint.query(1, 0, n - 1, 0, n - 1).val;
}

Compilation message

horses.cpp: In constructor 'Number::Number(int)':
horses.cpp:29:22: warning: declaration of 'val' shadows a member of 'Number' [-Wshadow]
   Number(int val = 1){
                      ^
horses.cpp:28:7: note: shadowed declaration is here
   int val;
       ^~~
horses.cpp: In member function 'Number Number::operator*(const Number&) const':
horses.cpp:36:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     result.val = 1LL * val * a.val % modulo;
                  ~~~~~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In member function 'Number Number::operator/(const Number&) const':
horses.cpp:47:32: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     result.val = 1LL * val * x % modulo;
                  ~~~~~~~~~~~~~~^~~~~~~~
horses.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
horses.cpp:69:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
horses.cpp: In member function 'void SegmentTree::computenode(int, int, int)':
horses.cpp:78:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 4 ms 632 KB Output is correct
24 Correct 4 ms 632 KB Output is correct
25 Correct 3 ms 632 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 632 KB Output is correct
28 Correct 3 ms 632 KB Output is correct
29 Correct 3 ms 632 KB Output is correct
30 Correct 3 ms 632 KB Output is correct
31 Correct 3 ms 632 KB Output is correct
32 Correct 3 ms 632 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 134588 KB Output is correct
2 Correct 916 ms 134860 KB Output is correct
3 Correct 859 ms 138360 KB Output is correct
4 Correct 907 ms 142204 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 400 KB Output is correct
23 Correct 4 ms 632 KB Output is correct
24 Correct 4 ms 632 KB Output is correct
25 Correct 3 ms 632 KB Output is correct
26 Correct 4 ms 632 KB Output is correct
27 Correct 3 ms 632 KB Output is correct
28 Correct 3 ms 632 KB Output is correct
29 Correct 3 ms 632 KB Output is correct
30 Correct 4 ms 632 KB Output is correct
31 Correct 3 ms 632 KB Output is correct
32 Correct 3 ms 632 KB Output is correct
33 Correct 584 ms 133880 KB Output is correct
34 Correct 571 ms 133884 KB Output is correct
35 Correct 677 ms 133892 KB Output is correct
36 Correct 671 ms 133880 KB Output is correct
37 Correct 519 ms 133752 KB Output is correct
38 Correct 620 ms 133752 KB Output is correct
39 Correct 508 ms 133752 KB Output is correct
40 Correct 648 ms 133756 KB Output is correct
41 Correct 501 ms 133800 KB Output is correct
42 Correct 504 ms 133664 KB Output is correct
43 Correct 632 ms 133624 KB Output is correct
44 Correct 623 ms 133496 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 296 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 4 ms 632 KB Output is correct
24 Correct 4 ms 636 KB Output is correct
25 Correct 4 ms 632 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 632 KB Output is correct
28 Correct 3 ms 760 KB Output is correct
29 Correct 3 ms 632 KB Output is correct
30 Correct 4 ms 632 KB Output is correct
31 Correct 3 ms 632 KB Output is correct
32 Correct 3 ms 632 KB Output is correct
33 Correct 706 ms 134620 KB Output is correct
34 Correct 906 ms 134648 KB Output is correct
35 Correct 867 ms 138160 KB Output is correct
36 Correct 928 ms 142036 KB Output is correct
37 Correct 594 ms 137396 KB Output is correct
38 Correct 570 ms 137464 KB Output is correct
39 Correct 670 ms 144424 KB Output is correct
40 Correct 675 ms 144412 KB Output is correct
41 Correct 528 ms 135604 KB Output is correct
42 Correct 634 ms 136540 KB Output is correct
43 Correct 526 ms 135520 KB Output is correct
44 Correct 649 ms 139388 KB Output is correct
45 Correct 510 ms 135612 KB Output is correct
46 Correct 504 ms 135676 KB Output is correct
47 Correct 622 ms 139840 KB Output is correct
48 Correct 628 ms 139936 KB Output is correct
49 Correct 802 ms 139712 KB Output is correct
50 Correct 802 ms 139636 KB Output is correct
51 Correct 739 ms 146292 KB Output is correct
52 Correct 747 ms 145856 KB Output is correct
53 Correct 706 ms 137824 KB Output is correct
54 Correct 704 ms 138476 KB Output is correct
55 Correct 611 ms 136532 KB Output is correct
56 Correct 782 ms 141304 KB Output is correct
57 Correct 554 ms 137168 KB Output is correct
58 Correct 574 ms 137720 KB Output is correct
59 Correct 630 ms 139880 KB Output is correct