제출 #1165593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165593		omtheprogrammer1	말 (IOI15_horses)	C++20	37 / 100	738 ms	70892 KiB

horses

#include <bits/stdc++.h>

using namespace std;
// #include "horses.h"

#define endl "\n"
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp make_pair
#define pb push_back
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define ins insert
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define sz(v) (ll)v.size()
#define readgraph(list, edges) for (ll i = 0; i < edges; i++) {ll a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define F_OR(i, a, b, s) for (ll i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)



mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
  return uniform_int_distribution<ll>(a, b)(mt_rng);
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const ll INF = 4e18;
const int d4i[4] = { -1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = { -1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int kni[8] = { +2, +2, -2, -2, 1, -1, 1, -1}, knj[8] = {1, -1, 1, -1, 2, 2, -2, -2};

ll n, m, k, q, l, r, x, y, z , h;
const ll tas = 1e6 + 10;
ll a[tas];
ll b[tas];
ll c[tas];
string s, t;
// vector<int> grid[tas];
// vector<pii> edges[tas];
ll ans = 0;

ll ismod = 0;

ll tree1[4 * tas];

void up1(int i, int l, int r, int in, ll val) {
  if (in < l || r < in) {
    return;
  }
  if (l == r) {
    tree1[i] = val;
    return;
  }
  int mid = (l + r) / 2;
  up1(2 * i + 1, l, mid, in, val);
  up1(2 * i + 2, mid + 1, r, in, val);
  tree1[i] = (tree1[2 * i + 1] * tree1[2 * i + 2]) % mod;
}

ll q1(int i, int l, int r, int tl, int tr) {
  if (tr < l || r < tl) {
    return 1;
  }
  if (tl <= l && r <= tr) {
    return tree1[i];
  }
  int mid = (l + r) / 2;
  ll x = q1(2 * i + 1, l, mid, tl, tr) ;
  ll y =     q1(2 * i + 2, mid + 1, r, tl, tr);
  if (x * y > ismod) {
    ismod = INF;
  }
  return (x * y) % mod;
}

ll tree2[4 * tas];

void up2(int i, int l, int r, int in, ll val) {
  if (in < l || r < in) {
    return;
  }
  if (l == r) {
    tree2[i] = val;
    return;
  }
  int mid = (l + r) / 2;
  up2(2 * i + 1, l, mid, in, val);
  up2(2 * i + 2, mid + 1, r, in, val);
  tree2[i] = max(tree2[2 * i + 1] , tree2[2 * i + 2]);
}

ll q2(int i, int l, int r, int tl, int tr) {
  if (tr < l || r < tl) {
    return -INF;
  }
  if (tl <= l && r <= tr) {
    // debug(tree2[i])
    return tree2[i];
  }
  int mid = (l + r) / 2;
  return max(q2(2 * i + 1, l, mid, tl, tr) ,
             q2(2 * i + 2, mid + 1, r, tl, tr));
}

set<int> se;
ll get(void) {
  if (se.empty()) {
    return q2(0, 0, n - 1, 0, n - 1);
  }
  // auto it = se.rbegin();
  auto it = se.rbegin();
  ll temp = 1;
  vector<pii> vec;
  FOR(sz(se)) {
    temp *= a[*it];
    vec.pb(mp(*it, a[*it]));
    // debug(*it)
    it++;
    if (temp >= 1e9) {
      break;
    }
  }
  // debug(vec)
  reverse(all(vec));
  vec.pb(mp(n, n));
  int tin = 0;
  ll cur = q2(0, 0, n - 1, vec[0].f, vec[1].f - 1);
  ll pre = 1;
  FOR(i, 1, sz(vec) - 1) {
    pre *= vec[i].s;
    ll t1 = pre * q2(0, 0, n - 1, vec[i].f, vec[i + 1].f - 1);
    // debug(i)
    if (t1 > cur) cur = t1, tin = i;
  }
  ismod = q2(0, 0, n - 1, 0, n - 1);
  ll l = q1(0, 0, n - 1, 0, vec[tin].f) ;
  ll r = q2(0, 0, n - 1, vec[tin].f, vec[tin + 1].f - 1);
  // if (l * r > ismod) {
  //   ismod = INF;
  // }
  // if (ismod == INF) {
    return (l * r) % mod;
  // }
  // return ismod;
}

int init(int N, int Xa[], int Ya[]) {
  n = N;
  FOR(4 * n + 10) tree1[i] = 1, tree2[i] = -INF;
  vector<int> X, Y;
  FOR(n) X.pb(Xa[i]);
  FOR(n) Y.pb(Ya[i]);
  // se.insert(n);
  int timer = 0;
  for (auto val : X) {
    a[timer] = val;
    if (val > 1) se.insert(timer);
    up1(0, 0, n - 1, timer++, val);
  }
  timer = 0;
  for (auto val : Y) {
    b[timer] = val;
    up2(0, 0, n - 1, timer++, val);
  }
  return get();
  return 0ll;
}

int updateX(int in, int val) {
  // in--;
  if (a[in] > 1) se.erase(in);
  if (val > 1)se.insert(in);
  up1(0, 0, n - 1, in, val);
  a[in] = val;
  return get();
}

int updateY(int in, int val) {
  // in--;
  b[in] = val;
  up2(0, 0, n - 1, in, val);
  return get();
}

// int main() {
//   fastio

// #ifdef LOCAL
//   auto begin = std::chrono::high_resolution_clock::now();
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   freopen("error.txt", "w", stderr);
// #endif

//   ll tc = 1;
//   ll N;
//   // cin >> N;
//   // vector<int> x, y;
//   // FOR(N) cin >> z, x.pb(z);
//   // FOR(N) cin >> z, y.pb(z);
//   // debug(init(N, x, y))
//   // debug(x)
//   // cin >> tc;
//   // for (int t = 0; t < tc; t++) solve(t);
// #ifdef LOCAL
//   auto end = std::chrono::high_resolution_clock::now();
//   auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//   cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
// #endif
// }

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