Submission #169904

#	Time	Username	Problem	Language	Result	Execution time	Memory
169904		AlexLuchianov	Horses (IOI15_horses)	C++14	100 / 100	928 ms	146292 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23