Submission #390610

#	Time	Username	Problem	Language	Result	Execution time	Memory
390610		WLZ	Horses (IOI15_horses)	C++14	17 / 100	1515 ms	83324 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

const int MOD = (int) 1e9 + 7;

int add(int a, int b) {
  if (a + b >= MOD) return a + b - MOD;
  return a + b;
}

int mul(int a, int b) {
  return (long long) a * b % MOD;
}

int n;
vector<int> x, y;
set<int> st;

struct node {
  int l, r, mx, pr;
  long long pr_ll;
  node *left, *right;
} *root;

node *build(int l, int r) {
  if (l == r) return new node{l, r, y[l], x[l], x[l], nullptr, nullptr};
  node *left = build(l, (l + r) / 2);
  node *right = build((l + r) / 2 + 1, r);
  return new node{l, r, max(left->mx, right->mx), mul(left->pr, right->pr), left->pr_ll * right->pr_ll, left, right};
}

void update(node *cur, int pos) {
  if (cur->l == cur->r) {
    cur->mx = y[pos], cur->pr = cur->pr_ll = x[pos];
    return;
  }
  if (pos <= cur->left->r) update(cur->left, pos);
  else update(cur->right, pos);
  cur->mx = max(cur->left->mx, cur->right->mx);
  cur->pr = mul(cur->left->pr, cur->right->pr);
  cur->pr_ll = cur->left->pr_ll * cur->right->pr_ll;
}

int query_mx(node *cur, int l, int r) {
  if (cur->l > r || cur->r < l) return 0;
  if (l <= cur->l && cur->r <= r) return cur->mx;
  return max(query_mx(cur->left, l, r), query_mx(cur->right, l, r));
}

int query_pr(node *cur, int l, int r) {
  if (cur->l > r || cur->r < l) return 1;
  if (l <= cur->l && cur->r <= r) return cur->pr;
  return mul(query_pr(cur->left, l, r), query_pr(cur->right, l, r));
}

long long query_pr_ll(node *cur, int l, int r) {
  if (cur->l > r || cur->r < l) return 1;
  if (l <= cur->l && cur->r <= r) return cur->pr_ll;
  return query_pr_ll(cur->left, l, r) * query_pr_ll(cur->right, l, r);
}

int calc_ans() {
  int i = 0, next = n, best = -1, best_next = -1;
  st.insert(0);
  for (auto it = st.rbegin(); it != st.rend() && i < 30; it = prev(it), i++) {
    if (best == -1 || query_mx(root, *it, next - 1) > query_pr_ll(root, *it + 1, best) * query_mx(root, best, best_next - 1)) best = *it, best_next = next;
    next = *it;
  }
  return mul(query_pr(root, 0, best), query_mx(root, best, best_next - 1));
}

int init(int N, int X[], int Y[]) {
  n = N;
  x.assign(X, X + n);
  y.assign(Y, Y + n);
  for (int i = 0; i < n; i++) if (x[i] != 1) st.insert(i);
  root = build(0, n - 1);
  return calc_ans();
}

int updateX(int pos, int val) {	
  if (x[pos] != val) {
    if (x[pos] == 1) {
      st.erase(pos);
    } else if (val == 1) {
      st.insert(pos);
    }
    x[pos] = val;
    update(root, pos);
  }
  return calc_ans();
}

int updateY(int pos, int val) {
  y[pos] = val;
  update(root, pos);
  return calc_ans();
}

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:13:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   13 |   return (long long) a * b % MOD;
      |          ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update(node*, int)':
horses.cpp:35:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   35 |     cur->mx = y[pos], cur->pr = cur->pr_ll = x[pos];

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