Submission #351471

#	Time	Username	Problem	Language	Result	Execution time	Memory
351471		spatarel	Horses (IOI15_horses)	C++17	100 / 100	478 ms	47340 KiB

horses

#include "horses.h"
#include <stdio.h>
#include <algorithm>
#include <set>

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

int N;
int X[MAX_N];

long long allProdX = 1;

long long power(long long base, int exp) {
  if (exp == 1) {
    return base;
  } else if (exp % 2 == 0) {
    return power(base * base % MOD, exp / 2);
  } else {
    return power(base, exp - 1) * base % MOD;
  }
}

int inv(int value) {
  return (int)power(value, MOD - 2);
}

struct Index {
  int index;
  int maxRangeY;
};

bool operator < (const Index &a, const Index &b) {
  return a.index < b.index;
}

int segTreeN = 1 << 19;
int segTree[1 << 20];

void segTreeUpdate(int index, int newValue) {
  index += segTreeN;
  segTree[index] = newValue;
  while (index > 1) {
    index /= 2;
    segTree[index] = std::max(segTree[2 * index], segTree[2 * index + 1]);
  }
}

int segTreeRangeMax(int left, int right) {
  right++;
  left += segTreeN;
  right += segTreeN;
  int answer = 0;
  while (left < right) {
    if (left % 2 == 1) {
      answer = std::max(answer, segTree[left]);
      left++;
    }
    if (right % 2 == 1) {
      right--;
      answer = std::max(answer, segTree[right]);
    }
    left /= 2;
    right /= 2;
  }
  return answer;
}

std::set<Index> relevantXs;

struct Fraction {
  int x;
  int y;
};

bool operator <(const Fraction &a, const Fraction &b) {
  // return a.x / a.y < b.x / b.y;
  return (long long)a.x * b.y < (long long)b.x * a.y;
}

int query() {
  Fraction answer = Fraction{1, 1};
  long long productX = 1;
  auto it = relevantXs.rbegin();
  while (it != relevantXs.rend() && productX < MOD) {
    answer = std::max(answer, Fraction{it->maxRangeY, (int)productX});
    
    productX *= X[it->index];
    it++;
  }
  //printf("%lld %d %d\n", allProdX, answer.x, answer.y);
  return int(allProdX * answer.x % MOD * inv(answer.y) % MOD);
}

int init(int n, int x[], int y[]) {
	int maxY = 0;
  N = n;
  for (int i = N - 1; i >= 0; i--) {
    X[i] = x[i];
    allProdX = allProdX * X[i] % MOD;
    segTreeUpdate(i, y[i]);
    maxY = std::max(maxY, y[i]);
    if (X[i] > 1 || i == 0) {
      relevantXs.insert(Index{i, maxY});
      maxY = 0;
    }
  }
  return query();
}

void dump() {
  for (Index index : relevantXs) {
    printf("(%d, %d) ", index.index, index.maxRangeY);
  }
}

int updateX(int pos, int val) {
	//printf("updateX(%d, %d)\n", pos, val);
  allProdX = allProdX * inv(X[pos]) % MOD;
  if (pos > 0 && X[pos] > 1) {
    // removeX(pos);
    //printf("removeX(%d) ", pos);
    //fflush(stdout);
    auto it = relevantXs.find(Index{pos, 0});
    //printf("done (%d, %d)!\n", it->index, it->maxRangeY);
    //fflush(stdout);
    int maxY2 = it->maxRangeY;
    auto prevIt = prev(it);
    //printf("done (%d, %d)!\n", it->index, it->maxRangeY);
    //fflush(stdout);
    relevantXs.erase(it);
    //printf("done!\n");
    //fflush(stdout);
    int maxY1 = prevIt->maxRangeY;
    int previousIndex = prevIt->index;
    relevantXs.erase(prevIt);
    //printf("done!\n");
    //fflush(stdout);
    relevantXs.insert(Index{previousIndex, std::max(maxY1, maxY2)});
    //printf("done!\n");
    //fflush(stdout);
  }
  X[pos] = val;
  allProdX = allProdX * X[pos] % MOD;
  if (pos > 0 && X[pos] > 1) {
    // insertX(pos);
    //printf("insertX(%d) ", pos);
    //fflush(stdout);
    int rightIndex, leftIndex;
    auto it = relevantXs.lower_bound(Index{pos, 0});
    if (it == relevantXs.end()) {
      rightIndex = N - 1;
    } else {
      rightIndex = it->index - 1;
    }
    auto prevIt = prev(it);
    leftIndex = prevIt->index;
    relevantXs.erase(prevIt);
    relevantXs.insert(Index{leftIndex, 
        segTreeRangeMax(leftIndex, pos - 1)});
    relevantXs.insert(Index{pos, 
        segTreeRangeMax(pos, rightIndex)});
    //printf("done!\n");
    //fflush(stdout);
  }
  //dump();
  return query();
}

int updateY(int pos, int val) {
  //printf("updateY(%d, %d)\n", pos, val);
	segTreeUpdate(pos, val);
  long long productX = 1;
  int prevIndex = N;
  auto it = relevantXs.end();
  it--;
  while (productX < MOD) {
    if (it->index <= pos && pos < prevIndex) {
      // it->maxRangeY = segTreeRangeMax(it->index, prevIndex - 1);
      int index = it->index;
      relevantXs.erase(it);
      relevantXs.insert(Index{index,
          segTreeRangeMax(index, prevIndex - 1)});
      break;
    }
    productX *= X[it->index];
    prevIndex = it->index;
    it--;
  }
  //dump();
  return query();
}

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