Submission #199729

#	Time	Username	Problem	Language	Result	Execution time	Memory
199729		FieryPhoenix	Horses (IOI15_horses)	C++11	100 / 100	452 ms	64888 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
 
int N;
ll worth[1005],X[500001],Y[500001];
bool over[1005];
set<int>bigInd;
ll treeMax[1000001],treeMult[1000001];
 
void updateMax(int pos, int 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(int L, int 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(int pos, int val){
  pos+=N;
  treeMult[pos]=val;
  for (pos/=2;pos>=1;pos/=2)
    treeMult[pos]=(treeMult[pos*2]*treeMult[pos*2+1])%MOD;
}
 
int queryMult(int L, int 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;
}
 
int calc(){
  if (bigInd.size()==0)
    return queryMax(0,N-1);
  vector<int>v;
  set<int>::iterator it=bigInd.end();
  it--;
  for (;;){
    v.push_back(*it);
    if (it==bigInd.begin() || v.size()==31)
      break;
    it--;
  }
  reverse(v.begin(),v.end());
  int M=v.size();
  for (int i=0;i<=M;i++){
    worth[i]=0;
    over[i]=false;
  }
  for (int i=M-1;i>=0;i--){
    if (over[i+1])
      worth[i]=X[v[i]]*worth[i+1];
    else{
      int L=v[i];
      int 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;
  }
  if (!over[0])
    return max(worth[0],queryMax(0,v[0]-1));
  return (worth[0]*queryMult(0,v[0]-1))%MOD;
}
 
int init(int n, int x[], int y[]){
  N=n;
  for (int 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]=val;
  updateMax(pos,val);
  return calc();
}
 

Compilation message (stderr)

horses.cpp: In function 'int queryMult(int, int)':
horses.cpp:79:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ans;
          ^~~
horses.cpp: In function 'int calc()':
horses.cpp:84:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return queryMax(0,N-1);
            ~~~~~~~~^~~~~~~
horses.cpp:95:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int M=v.size();
         ~~~~~~^~
horses.cpp:118:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return max(worth[0],queryMax(0,v[0]-1));
            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:119:40: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return (worth[0]*queryMult(0,v[0]-1))%MOD;
                                        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:127:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMax(i,Y[i]);
                 ~~~^
horses.cpp:128:21: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMult(i,X[i]);
                  ~~~^

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