Submission #1293198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293198		DeltaStruct	Horses (IOI15_horses)	C++20	100 / 100	135 ms	52372 KiB

horses

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

int n; long long mod=1e9+7,inf=1e9+1;
using segtype = tuple<long long,long long,long long,long long,int,long long>;
// answer mod,min(answer,1e9+1),min(width,1e9+1),min(answer_width,1e9+1),max_value,width mod
vector<segtype> segtree;
segtype f(segtype x,segtype y){
  auto [a,b,c,d,e,k] = x; auto [f,g,h,i,j,l] = y;
  if (e>=d*g) return make_tuple(a,b,min(c*h,inf),min(d*h,inf),e,(k*l)%mod);
  return make_tuple((f*k)%mod,min(g*k,inf),min(c*h,inf),i,j,(k*l)%mod);
}
segtype id = make_tuple(0,0,1,1,0,1);
int res(){
  segtype ll = id,rr = id;
  for (int l(n),r(n+n);l < r;l>>=1,r>>=1){
    if (l&1) ll = f(ll,segtree[l++]);
    if (r&1) rr = f(segtree[--r],rr);
  }
  return get<0>(f(ll,rr));
}

int init(int nn,int A[],int B[]){
  n = nn,segtree.assign(2*n,id),swap(A,B);
  for (int i(0);i < n;++i) segtree[n+i] = make_tuple(
    ((long long)A[i]*B[i])%mod,
    min((long long)A[i]*B[i],inf),
    B[i],
    1,
    A[i],
    B[i]
  );
  for (int i(n-1);i;--i) segtree[i] = f(segtree[i<<1],segtree[i<<1|1]);
  return res();
}

int updateX(int x,int y){
  int z = get<4>(segtree[n+x]);
  segtree[n+x] = make_tuple( ((long long)y*z)%mod, min((long long)y*z,inf), y, 1, z, y );
  for (int l((n+x)>>1);l;l>>=1) segtree[l] = f(segtree[l<<1],segtree[l<<1|1]);
  return res();
}

int updateY(int x,int y){
  int z = get<5>(segtree[n+x]); swap(y,z);
  segtree[n+x] = make_tuple( ((long long)y*z)%mod, min((long long)y*z,inf), y, 1, z, y );
  for (int l((n+x)>>1);l;l>>=1) segtree[l] = f(segtree[l<<1],segtree[l<<1|1]);
  return res();
}

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