Submission #199725

#	Time	Username	Problem	Language	Result	Execution time	Memory
199725		FieryPhoenix	Horses (IOI15_horses)	C++11	37 / 100	434 ms	52472 KiB

horses

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include <horses.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
 
ll N;
ll worth[100005],X[500001],Y[500001];
bool over[100005];
set<ll>bigInd;
ll treeMax[1000001],treeMult[1000001];
 
void updateMax(ll pos, ll val){
  pos+=N;
  treeMax[pos]=val;
  for (pos/=2;pos>=1;pos/=2)
    treeMax[pos]=max(treeMax[pos*2],treeMax[pos*2+1]);
}
 
ll queryMax(ll L, ll R){
  L+=N; R+=N;
  ll ans=0;
  while (L<=R){
    if (L%2==1)
      ans=max(ans,treeMax[L++]);
    if (R%2==0)
      ans=max(ans,treeMax[R--]);
    L/=2;
    R/=2;
  }
  return ans;
}
 
void updateMult(ll pos, ll val){
  pos+=N;
  treeMult[pos]=val;
  for (pos/=2;pos>=1;pos/=2)
    treeMult[pos]=(treeMult[pos*2]*treeMult[pos*2+1])%MOD;
}
 
ll queryMult(ll L, ll R){
  L+=N; R+=N;
  ll ans=1;
  while (L<=R){
    if (L%2==1)
      ans*=treeMult[L++];
    ans%=MOD;
    if (R%2==0)
      ans*=treeMult[R--];
    ans%=MOD;
    L/=2;
    R/=2;
  }
  return ans;
}
 
ll calc(){
  if (bigInd.size()==0)
    return queryMax(0,N-1);
  vector<ll>v;
  set<ll>::iterator it=bigInd.end();
  it--;
  for (;;){
    v.push_back(*it);
    if (it==bigInd.begin() || v.size()==31)
      break;
    it--;
  }
  reverse(v.begin(),v.end());
  ll M=v.size();
  for (ll i=0;i<=M;i++){
    worth[i]=0;
    over[i]=false;
  }
  for (ll i=M-1;i>=0;i--){
    if (over[i+1])
      worth[i]=X[v[i]]*worth[i+1];
    else{
      ll L=v[i];
      ll R;
      if (i==M-1)
	R=N-1;
      else
	R=v[i+1]-1;
      assert(L<=R);
      worth[i]=X[v[i]]*max(queryMax(L,R),worth[i+1]);
    }
    over[i]=(worth[i]>1000000000) | over[i+1];
    if (over[i])
      worth[i]%=MOD;
  }
  return (worth[0]*queryMult(0,v[0]-1))%MOD;
}
 
int init(int n, int x[], int y[]){
  N=n;
  for (ll i=0;i<N;i++){
    X[i]=x[i];
    Y[i]=y[i];
    updateMax(i,Y[i]);
    updateMult(i,X[i]);
    if (X[i]>1)
      bigInd.insert(i);
  }
  return calc();
}
 
int updateX(int pos, int val){
  if (X[pos]>1 && val==1)
    bigInd.erase(pos);
  else if (X[pos]==1 && val>1)
    bigInd.insert(pos);
  X[pos]=val;
  updateMult(pos,val);
  return calc();
}
 
int updateY(int pos, int val){
  Y[pos]=(ll)val;
  updateMax((ll)pos,(ll)val);
  return calc();
}
 

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:130:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return calc();
          ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:140:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return calc();
          ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return calc();
          ~~~~^~

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