Submission #720436

#	Time	Username	Problem	Language	Result	Execution time	Memory
720436		abczz	Horses (IOI15_horses)	C++14	100 / 100	633 ms	73292 KiB

horses

#include <iostream>
#include <map>
#include <horses.h>
#define ll long long
int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);

using namespace std;

const ll M = 1e9 + 7;
map <ll, ll> mp;
ll n, st[2000000], st2[2000000], A[500000], B[500000];

void build(ll id, ll l, ll r) {
  if (l == r) {
    st[id] = A[l];
    return;
  }
  ll mid = (l+r)/2;
  build(id*2, l, mid);
  build(id*2+1, mid+1, r);
  st[id] = (st[id*2]*st[id*2+1])%M;
}

void build2(ll id, ll l, ll r) {
  if (l == r) {
    st2[id] = B[l];
    return;
  }
  ll mid = (l+r)/2;
  build2(id*2, l, mid);
  build2(id*2+1, mid+1, r);
  st2[id] = max(st2[id*2], st2[id*2+1]);
}

void update(ll id, ll l, ll r, ll q, ll v) {
  if (l == r) {
    st[id] = v;
    return;
  }
  ll mid = (l+r)/2;
  if (q <= mid) update(id*2, l, mid, q, v);
  else update(id*2+1, mid+1, r, q, v);
  st[id] = (st[id*2]*st[id*2+1])%M;
}

void update2(ll id, ll l, ll r, ll q, ll v) {
  if (l == r) {
    st2[id] = v;
    return;
  }
  ll mid = (l+r)/2;
  if (q <= mid) update2(id*2, l, mid, q, v);
  else update2(id*2+1, mid+1, r, q, v);
  st2[id] = max(st2[id*2], st2[id*2+1]);
}

ll query(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql) return 1;
  else if (ql <= l && r <= qr) return st[id];
  ll mid = (l+r)/2;
  return (query(id*2, l, mid, ql, qr)*query(id*2+1, mid+1, r, ql, qr))%M;
}

ll query2(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql) return -1;
  else if (ql <= l && r <= qr) return st2[id];
  ll mid = (l+r)/2;
  return max(query2(id*2, l, mid, ql, qr),query2(id*2+1, mid+1, r, ql, qr));
}

ll solve() {
  ll f = -1, j, p = n-1, res, z;
  if (mp.empty()) return query2(1, 0, n-1, 0, n-1); 
  auto itr = prev(mp.end());
  while (true) {
    if (itr->first != p) {
      res = query2(1, 0, n-1, itr->first, p);
      if (f < res) {
        f = z = res;
        j = itr->first;
      }
    }
    else if (f < B[itr->first]) {
      f = z = B[itr->first];
      j = itr->first;
    }
    f *= A[itr->first];
    p = itr->first-1;
    if (f >= M) break;
    else if (itr == mp.begin()) {
      if (p) {
        res = query2(1, 0, n-1, 0, p);
        if (f < res) return res;
      }
      break;
    }
    itr = prev(itr);
  }
  return (query(1, 0, n-1, 0, j)*z)%M;
}

int init(int N, int X[], int Y[]) {
  n = N;
  for (int i=0; i<n; ++i) {
    A[i] = X[i];
    B[i] = Y[i];
    if (A[i] != 1) ++mp[i];
  }
  build(1, 0, n-1);
  build2(1, 0, n-1);
  return solve();
}

int updateX(int pos, int val) {
  if (A[pos] != 1 && val == 1) mp.erase(pos);
  else if (A[pos] == 1 && val != 1) ++mp[pos];
  A[pos] = val;
  update(1, 0, n-1, pos, val);
  return solve();
}

int updateY(int pos, int val) {
  B[pos] = val;
  update2(1, 0, n-1, pos, val);
  return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:113:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |   return solve();
      |          ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |   return solve();
      |          ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |   return solve();
      |          ~~~~~^~
horses.cpp: In function 'long long int solve()':
horses.cpp:101:33: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |   return (query(1, 0, n-1, 0, j)*z)%M;
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:101:16: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |   return (query(1, 0, n-1, 0, j)*z)%M;
      |           ~~~~~^~~~~~~~~~~~~~~~~

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