Submission #785657

#	Time	Username	Problem	Language	Result	Execution time	Memory
785657		I_Love_EliskaM_	Horses (IOI15_horses)	C++14	100 / 100	425 ms	41276 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int mod = 1e9+7;

#define int long long
int pw(int a, int b) {
  int r=1;
  while (b) {
    if (b&1) r=(r*a)%mod;
    a=(a*a)%mod;
    b>>=1;
  }
  return r;
}
int inv(int x) {
  return pw(x,mod-2);
}

struct BIT {
  vector<int> t; int n;
  BIT(int n) {
    this->n=n;
    t.assign(n,1);
  }
  void add(int i, int x) {
    for(;i<n;i=i|(i+1)) t[i]=(t[i]*x)%mod;
  }
  int sum(int r) {
    int q=1;
    for(;r>=0;r=(r&(r+1))-1) q=(q*t[r])%mod;
    return q;
  }
};
#undef int

int a[(int)5e5+5];
int c[(int)5e5+5];
BIT ft(5e5+5);
set<int> s;
int n;

struct sgt {
  vector<int> t; int sz=1;
  sgt(int n) {
    while (sz<n) sz<<=1;
    t.assign(2*sz,0);
  }
  int query(int v, int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return 0;
    if (lx<=l && r<=rx) return t[v];
    int m=(l+r)>>1;
    int lq=query(2*v+1,l,m,lx,rx);
    int rq=query(2*v+2,m,r,lx,rx);
    return max(lq,rq);
  }
  int query(int l, int r) {
    return query(0,0,sz,l,r);
  }

  void upd(int v, int l, int r, int i) {
    if (r-l==1) return;
    int m=(l+r)>>1;
    if (i<m) upd(2*v+1,l,m,i);
    else upd(2*v+2,m,r,i);
    t[v]=max(t[2*v+1],t[2*v+2]);
  }
  void set(int i, int x) {
    t[sz-1+i]=x;
    upd(0,0,sz,i);
  }
};
sgt st(5e5+5);

int query() {
  #define int long long
  int z=1;
  int b=0;
  pi mx={0,1};
  int last=n;
  s.insert(0);
  for (auto v:s) {
    int i=-v;
    if (z>1e9) break;
    int y=st.query(i,n);
    if (y*mx.s>mx.f*z) {
      b=i;
      mx={y,z};
    }
    z*=a[i];
    last=i;
  }
  int p=ft.sum(b);
  int y=st.query(b,n);
  return (p*y)%mod;
  #undef int
}

int init(int _n, int x[], int y[]) { 
  n=_n;
  forn(i,n) a[i]=x[i], c[i]=y[i];
  forn(i,n) ft.add(i,a[i]);
  forn(i,n) if (a[i]>1) s.insert(-i);
  forn(i,n) st.set(i,c[i]);
  return query();
}
int updateX(int i, int x) {
  if (a[i]>1) s.erase(s.find(-i));
  ft.add(i,inv(a[i]));
  a[i]=x;
  if (a[i]>1) s.insert(-i);
  ft.add(i,a[i]);
  return query();
}
int updateY(int i, int x) {
  c[i]=x;
  st.set(i,c[i]);
  return query();
}

Compilation message (stderr)

horses.cpp: In constructor 'BIT::BIT(long long int)':
horses.cpp:28:11: warning: declaration of 'n' shadows a member of 'BIT' [-Wshadow]
   28 |   BIT(int n) {
      |           ^
horses.cpp:27:22: note: shadowed declaration is here
   27 |   vector<int> t; int n;
      |                      ^
horses.cpp: In constructor 'BIT::BIT(long long int)':
horses.cpp:28:11: warning: declaration of 'n' shadows a member of 'BIT' [-Wshadow]
   28 |   BIT(int n) {
      |           ^
horses.cpp:27:22: note: shadowed declaration is here
   27 |   vector<int> t; int n;
      |                      ^
horses.cpp: In constructor 'BIT::BIT(long long int)':
horses.cpp:28:11: warning: declaration of 'n' shadows a member of 'BIT' [-Wshadow]
   28 |   BIT(int n) {
      |           ^
horses.cpp:27:22: note: shadowed declaration is here
   27 |   vector<int> t; int n;
      |                      ^
horses.cpp: In constructor 'sgt::sgt(int)':
horses.cpp:51:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   51 |   sgt(int n) {
      |       ~~~~^
horses.cpp:47:5: note: shadowed declaration is here
   47 | int n;
      |     ^
horses.cpp: In constructor 'sgt::sgt(int)':
horses.cpp:51:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   51 |   sgt(int n) {
      |       ~~~~^
horses.cpp:47:5: note: shadowed declaration is here
   47 | int n;
      |     ^
horses.cpp: In constructor 'sgt::sgt(int)':
horses.cpp:51:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   51 |   sgt(int n) {
      |       ~~~~^
horses.cpp:47:5: note: shadowed declaration is here
   47 | int n;
      |     ^
horses.cpp: In function 'int query()':
horses.cpp:90:9: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   90 |     if (z>1e9) break;
      |         ^
horses.cpp:91:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |     int y=st.query(i,n);
      |                    ^
horses.cpp:100:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 |   int y=st.query(b,n);
      |                  ^
horses.cpp:101:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |   return (p*y)%mod;
      |          ~~~~~^~~~
horses.cpp:86:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   86 |   int last=n;
      |       ^~~~

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