Submission #96198

#	Time	Username	Problem	Language	Result	Execution time	Memory
96198		tincamatei	Horses (IOI15_horses)	C++14	100 / 100	637 ms	61020 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000;
const int MOD = 1000000007;

template<typename T, typename Upd>
struct Aint {
  T aint[1+4*MAX_N];
  T neutralQry, initVal;
  Upd upd;

  Aint(T nq, T iv) {
    neutralQry = nq;
    initVal = iv;
    for(int i = 0; i <= 4*MAX_N; ++i)
      aint[i] = initVal;
  }

  void update(int poz, T val, int l = 1, int r = MAX_N, int nod = 1) {
    if(poz < l || r < poz) return;
    if(l == r)
      aint[nod] = upd.update(aint[nod], val);
    else {
      int mid = (l + r) / 2;
      update(poz, val, l, mid, 2 * nod);
      update(poz, val, mid + 1, r, 2 * nod + 1);
      aint[nod] = upd.query(aint[2 * nod], aint[2 * nod + 1]);
    }
  }

  T query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
    if(j < l || r < i) return neutralQry;
    if(i <= l && r <= j) return aint[nod];
    else {
      int mid = (l + r) / 2;
      return upd.query(query(i, j, l, mid, 2 * nod),
                        query(i, j, mid + 1, r, 2 * nod + 1));
    }
  }
};

struct Upd1 {
  int update(int a, int b) { return b; }
  int query(int a, int b)  { return max(a, b); }
};

struct Upd2 {
  int update(int a, int b) { return b; }
  int query(int a, int b)  { return (long long)a * b % MOD;}
};

int N;
int x[1+MAX_N], y[1+MAX_N];

set<int> rel;

Aint<int, Upd1> maxaint(-1, -1);
Aint<int, Upd2> prodaint(1, 1);

int getResult() {
  long long best, rez;
  best = rez = 0;
  set<int>::reverse_iterator it = rel.rbegin();

  while(it != rel.rend() && best != -1) {
    int pos = *it, maxy = maxaint.query(max(1, pos), N);
    if(maxy > best) {
      best = maxy;
      rez = (long long)prodaint.query(1, max(1, pos)) * maxy % MOD;
    }

    if(best <= 1000000000 / x[pos])
      best = best * x[pos];
    else
      best = -1;
    it++;
  }

  return rez;
}

int init(int n, int _x[], int _y[]) {
  N = n;
  x[0] = y[0] = 1;
  rel.insert(0);
  for(int i = 1; i <= n; ++i) {
    x[i] = _x[i - 1];
    y[i] = _y[i - 1];
    if(x[i] != 1)
      rel.insert(i);
    maxaint.update(i, y[i]);
    prodaint.update(i, x[i]);
  }
  return getResult();
}

int updateX(int pos, int val) {
  pos++;

  rel.erase(pos);
  x[pos] = val;
  if(val != 1)
    rel.insert(pos);

  prodaint.update(pos, val);
  return getResult();
}

int updateY(int pos, int val) {
  pos++;
  y[pos] = val;
  maxaint.update(pos, val);
  return getResult();
}

Compilation message (stderr)

horses.cpp: In member function 'int Upd1::update(int, int)':
horses.cpp:46:18: warning: unused parameter 'a' [-Wunused-parameter]
   int update(int a, int b) { return b; }
                  ^
horses.cpp: In member function 'int Upd2::update(int, int)':
horses.cpp:51:18: warning: unused parameter 'a' [-Wunused-parameter]
   int update(int a, int b) { return b; }
                  ^
horses.cpp: In member function 'int Upd2::query(int, int)':
horses.cpp:52:54: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   int query(int a, int b)  { return (long long)a * b % MOD;}
                                     ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getResult()':
horses.cpp:82:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return rez;
          ^~~

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