제출 #238159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238159		rama_pang	말 (IOI15_horses)	C++14	34 / 100	1584 ms	18048 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

// It is always optimal to sell all horses in a single year

class SegmentTree {
 private:
  struct Mint {
    int val = 0;
    bool overflow = 0;
    const Mint operator * (const Mint &x) const {
      return {(int) (1ll * this->val * x.val % mod), 
          (bool) (this->overflow || x.overflow || (1ll * this->val * x.val >= mod))};
    }
  };

  int sz;
  vector<Mint> X;
  vector<int> Y;
  vector<int> optimal;

  void Pull(int n, int lc, int rc) {
    X[n] = X[lc] * X[rc];
    Mint in_between = QueryX(1, 0, sz - 1, optimal[lc] + 1, optimal[rc]);
    if (in_between.overflow) {
      optimal[n] = optimal[rc];
    } else if (Y[optimal[lc]] > 1ll * Y[optimal[rc]] * in_between.val) {
      optimal[n] = optimal[lc];
    } else {
      optimal[n] = optimal[rc];
    }
  }

  Mint QueryX(int n, int tl, int tr, int l, int r) {
    if (tr < l || r < tl || tl > tr || l > r) return Mint({1, 0});
    if (l <= tl && tr <= r) return X[n];
    int mid = (tl + tr) / 2;
    int z = n + 2 * (mid - tl + 1);
    return QueryX(n + 1, tl, mid, l, r) * QueryX(z, mid + 1, tr, l, r);
  }

  void UpdateX(int n, int tl, int tr, int p, int x) {
    if (tl == tr) {
      X[n] = {x, 0};
      return;
    }
    int mid = (tl + tr) / 2;
    int z = n + 2 * (mid - tl + 1);
    if (p <= mid) {
      UpdateX(n + 1, tl, mid, p, x);
    } else {
      UpdateX(z, mid + 1, tr, p, x);
    }
    return Pull(n, n + 1, z);
  }

  void UpdateY(int n, int tl, int tr, int p, int x) {
    if (tl == tr) {
      Y[tl] = x;
      return;
    }
    int mid = (tl + tr) / 2;
    int z = n + 2 * (mid - tl + 1);
    if (p <= mid) {
      UpdateY(n + 1, tl, mid, p, x);
    } else {
      UpdateY(z, mid + 1, tr, p, x);
    }
    return Pull(n, n + 1, z);
  }

  void Build(int n, int tl, int tr) {
    if (tl == tr) {
      optimal[n] = tl;
      return;
    }
    int mid = (tl + tr) / 2;
    int z = n + 2 * (mid - tl + 1);
    Build(n + 1, tl, mid);
    Build(z, mid + 1, tr);
    optimal[n] = optimal[z];
  }

 public:
  SegmentTree() {}
  SegmentTree(int n) : sz(n) {
    X.assign(2 * sz, Mint({1, 0}));
    Y.assign(sz, 0);
    optimal.assign(2 * sz, 0);
    Build(1, 0, sz - 1);
  }

  void UpdateX(int p, int x) {
    return UpdateX(1, 0, sz - 1, p, x);
  }
  void UpdateY(int p, int x) {
    return UpdateY(1, 0, sz - 1, p, x);
  }
  int Query() {
    return 1ll * QueryX(1, 0, sz - 1, 0, optimal[1]).val * Y[optimal[1]] % mod;
  }
};

SegmentTree segtree;

int init(int N, int X[], int Y[]) {
  segtree = SegmentTree(N);
  for (int i = 0; i < N; i++) {
    segtree.UpdateX(i, X[i]);
    segtree.UpdateY(i, Y[i]);
  }
	return segtree.Query();
}

int updateX(int pos, int val) {	
  segtree.UpdateX(pos, val);
  return segtree.Query();
}

int updateY(int pos, int val) {
	segtree.UpdateY(pos, val);
  return segtree.Query();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In member function 'int SegmentTree::Query()':
horses.cpp:102:74: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return 1ll * QueryX(1, 0, sz - 1, 0, optimal[1]).val * Y[optimal[1]] % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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