Submission #645987

#	Time	Username	Problem	Language	Result	Execution time	Memory
645987		NintsiChkhaidze	Horses (IOI15_horses)	C++14	100 / 100	1160 ms	50256 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int mod = 1000000007,N = 500005;
ll x[N],y[N],ans;
int n;

struct {
  ll nam;
  ll maxy;
  int id;
//id = (l,r) shualedshi 1sgan(x[i]) gansxvavebuli sul marjvena ricxvis indexi
} t[4*N];

void upd(int h,int l,int r,int idx){
  if (l == r){
    t[h].id = 0;
    if (x[l] != 1) t[h].id = l;
    t[h].nam = x[l];
    t[h].maxy = y[l];
    return;
  }

  if (idx > (l + r)/2) upd(right,idx);
  else upd(left,idx);

  if (x[t[h*2 + 1].id] > 1){
    t[h].id = t[h*2 + 1].id;
  }else if (x[t[h*2].id] > 1){
    t[h].id =t[h*2].id;
  }else{
    t[h].id=0;
  }
  
  t[h].maxy = max(t[h*2].maxy, t[h*2+1].maxy);
  t[h].nam = (t[h*2].nam * t[h*2+1].nam)%mod;
}

ll getnam (int h,int l,int r,int L,int R){
  if (r < L || R < l) return 1;
  if (L <= l && r <= R) return t[h].nam;
  ll X = getnam(left,L,R),Y = getnam(right,L,R);
  return (X*Y)%mod;
}

ll getid(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 0LL;
  if (L <= l && r <= R) return t[h].id;
  int X = getid(left,L,R),Y = getid(right,L,R);
  if (x[Y] > 1) return Y;
  if (x[X] > 1) return X;
  return 0;
}

ll getmaxy(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 0LL;
  if (L <= l && r <= R) return t[h].maxy;
  return max(getmaxy(left,L,R),getmaxy(right,L,R));
}

void go(){
  vector <pair<ll,ll>> vec; vec.clear();
  int r = n;

  for (int o = 1; o <= 60; o++){
    if (r < 1) break;
    if (x[r] != 1LL) {
      vec.pb({x[r],y[r]});
      r--;
      continue;
    }
    int res = getid(1,1,n,1,r) + 1;
    vec.pb({1LL,getmaxy(1,1,n,res,r)});
    r = res - 1;
  }
  
  reverse(vec.begin(),vec.end());  
  ll k = 1LL,yy = vec[0].s,p = vec[0].f;
  bool q=0;
  ans = (p*yy)%mod;
  for (int j = 1; j<vec.size(); j++){
    ll X = vec[j].f,Y = vec[j].s;
    p = (p * X)%mod;
    if (!q && k < 1e9) k *= X;
    if (k >= 1e9) q=1;

    if (q || (k*Y >= yy)){
      yy = Y;
      ans = (p * Y)%mod;
      k=1LL; q=0;
    }
  }
  
  ans = (ans * getnam(1,1,n,1,r))%mod;
}

int init(int N, int X[], int Y[]) {
  n=N;
  for (int i = 1;i <= n; i++)
    x[i] = X[i-1],y[i] = Y[i-1],upd(1,1,n,i);

  go();
	return ans;
}

int updateX(int pos, int val) {	
  pos++;
  x[pos] = val;
  upd(1,1,n,pos);
  go();
	return ans;
}

int updateY(int pos, int val) {
  pos++;
  y[pos]=val;
  upd(1,1,n,pos);
  go();
	return ans;
}

Compilation message (stderr)

horses.cpp: In function 'long long int getid(int, int, int, int, int)':
horses.cpp:56:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |   int X = getid(left,L,R),Y = getid(right,L,R);
      |           ~~~~~^~~~~~~~~~
horses.cpp:56:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |   int X = getid(left,L,R),Y = getid(right,L,R);
      |                               ~~~~~^~~~~~~~~~~
horses.cpp: In function 'void go()':
horses.cpp:79:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |     int res = getid(1,1,n,1,r) + 1;
      |               ~~~~~~~~~~~~~~~~~^~~
horses.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int j = 1; j<vec.size(); j++){
      |                   ~^~~~~~~~~~~
horses.cpp:91:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   91 |     if (!q && k < 1e9) k *= X;
      |               ^
horses.cpp:92:9: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   92 |     if (k >= 1e9) q=1;
      |         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  104 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:11:28: note: shadowed declaration is here
   11 | const int mod = 1000000007,N = 500005;
      |                            ^
horses.cpp:110:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:118:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  118 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:126:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |  return ans;
      |         ^~~

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