Submission #127894

#	Time	Username	Problem	Language	Result	Execution time	Memory
127894		ekrem	Horses (IOI15_horses)	C++98	17 / 100	928 ms	65528 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;

ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
set < ll > s;
set < ll > :: iterator it;

ll islem(ll d, ll a, ll b){
  if(!d)
    return max(a, b);
  return 1ll*a*b%mod;
}

void bu(ll d, ll k, ll bas, ll son){
  if(bas == son){
    seg[d][k] = (!d)?y[bas]:x[bas];
    return;
  }
  bu(d, sol, bas, orta);
  bu(d, sag, orta + 1, son);
  seg[d][k] = islem(d, seg[d][sol], seg[d][sag]);
}

void up(ll d, ll k, ll bas, ll son, ll x, ll y){
  if(bas == son){
    seg[d][k] = y;
    return;
  }
  if(x <= orta)
    up(d, sol, bas, orta, x, y);
  else
    up(d, sag, orta + 1, son, x, y);
  seg[d][k] = islem(d, seg[d][sol], seg[d][sag]);
}

ll qu(ll d, ll k, ll bas, ll son, ll x, ll y){
  if(bas > y or son < x)
    return 1;
  if(bas >= x and son <= y)
    return seg[d][k];
  return islem(d, qu(d, sol, bas, orta, x, y), qu(d, sag, orta + 1, son, x, y));
}

ll ansbul(){
  if(s.size() == 1)
    return qu(0, 1, 1, n, 1, n);
  k = 0;
  ll of = 1;
  it = s.end();it--;
  while(1){
    z[++k] = *it;
    // cout << *it << endl;
    of = of*x[z[k]];
    if(it == s.begin())
      break;
    it--;
    // cout << of << endl;
    if(of > inf){
      // k--;
      break;
    }
  }
  reverse(z + 1, z + k + 1);
  // for(ll i = 1; i <= k; i++)cout << x[z[i]] << " ";cout << endl;
  ll crp = qu(1, 1, 1, n, 1, z[1] - 1), mx = 1, su = 1;
  for(ll i = 1; i < k; i++){
    su *= x[z[i]];
    mx = max(mx, 1ll*qu(0, 1, 1, n, z[i], z[i + 1] - 1)*su);
    // if(1ll*qu(0, 1, 1, n, z[i], z[i + 1] - 1)*su < 0)assert(0);
  }
  return (mx%mod)*crp%mod;
}

int init(int nn, int X[], int Y[]) {n = nn;
  x[n + 1] = 1;
  for(ll i = 1; i <= n; i++){
    x[i] = X[i - 1];
    y[i] = Y[i - 1];
  }
  bu(0, 1, 1, n);
  bu(1, 1, 1, n);
  for(ll i = 1; i <= n; i++)
    if(x[i] > 1)
      s.insert(i);
  s.insert(n + 1);
  return ansbul();
}

int updateX(int pos, int val) {pos++;
  s.erase(pos);
  x[pos] = val;
  up(1, 1, 1, n, pos, val);
  if(val > 1)
    s.insert(pos);
  return ansbul();
}

int updateY(int pos, int val) {pos++;
  up(0, 1, 1, n, pos, val);
  return ansbul();
}

Compilation message (stderr)

horses.cpp: In function 'void bu(ll, ll, ll, ll)':
horses.cpp:29:35: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 void bu(ll d, ll k, ll bas, ll son){
                                   ^
horses.cpp:19:7: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
       ^
horses.cpp: In function 'void up(ll, ll, ll, ll, ll, ll)':
horses.cpp:39:47: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 void up(ll d, ll k, ll bas, ll son, ll x, ll y){
                                               ^
horses.cpp:19:23: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
                       ^
horses.cpp:39:47: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void up(ll d, ll k, ll bas, ll son, ll x, ll y){
                                               ^
horses.cpp:19:14: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
              ^
horses.cpp:39:47: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 void up(ll d, ll k, ll bas, ll son, ll x, ll y){
                                               ^
horses.cpp:19:7: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
       ^
horses.cpp: In function 'll qu(ll, ll, ll, ll, ll, ll)':
horses.cpp:51:45: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 ll qu(ll d, ll k, ll bas, ll son, ll x, ll y){
                                             ^
horses.cpp:19:23: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
                       ^
horses.cpp:51:45: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 ll qu(ll d, ll k, ll bas, ll son, ll x, ll y){
                                             ^
horses.cpp:19:14: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
              ^
horses.cpp:51:45: warning: declaration of 'k' shadows a global declaration [-Wshadow]
 ll qu(ll d, ll k, ll bas, ll son, ll x, ll y){
                                             ^
horses.cpp:19:7: note: shadowed declaration is here
 ll n, k, kk, x[MAXN], y[MAXN], z[MAXN], seg[2][4*MAXN];
       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ansbul();
          ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ansbul();
          ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:115:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ansbul();
          ~~~~~~^~

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