Submission #409044

#	Time	Username	Problem	Language	Result	Execution time	Memory
409044		urd05	Horses (IOI15_horses)	C++14	17 / 100	932 ms	45380 KiB

horses

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

int n;
long long x[500000];
long long y[500000];
long long all=1;
const int mod=1e9+7;
const int sz=524288;
int seg[sz*2];
set<int> s;
typedef pair<long long,long long> P;

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,int val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }
}

long long fastpow(long long a,long long b) {
    if (b==0) {
        return 1;
    }
    if (b%2==1) {
        return (fastpow(a,b-1)*a)%mod;
    }
    long long half=fastpow(a,b/2);
    return (half*half)%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];
        update(i,y[i]);
        all*=x[i];
        all%=mod;
        if (x[i]!=1) {
            s.insert(i);
        }
    }
    int pr=-1;
    P mx=P(0,1);
    long long gop=1;
    if (s.empty()) {
        return sum(0,n-1);
    }
    auto iter=prev(s.end());
    pr=n;
    while (1) {
        int now=*iter;
        if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
            mx=P(sum(now,pr-1),gop);
        }
        gop*=x[now];
        if (gop>mod||iter==s.begin()) {
            break;
        }
        iter--;
        pr=now;
    }
	long long val=mx.first*fastpow(mx.second,mod-2);
	val%=mod;
	return (all*val)%mod;
}

int updateX(int pos, int val) {
    if (x[pos]!=1&&val==1) {
        s.erase(pos);
    }
    else if (x[pos]==1&&val!=1) {
        s.insert(pos);
    }
    x[pos]=val;
    P mx=P(0,1);
    long long gop=1;
    if (s.empty()) {
        return sum(0,n-1);
    }
    auto iter=prev(s.end());
    int pr=n;
    while (1) {
        int now=*iter;
        if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
            mx=P(sum(now,pr-1),gop);
        }
        gop*=x[now];
        if (gop>mod||iter==s.begin()) {
            break;
        }
        pr=now;
        iter--;
    }
	long long vl=mx.first*fastpow(mx.second,mod-2);
	vl%=mod;
	return (all*vl)%mod;
}

int updateY(int pos, int val) {
    update(pos,val);
    P mx=P(0,1);
    long long gop=1;
    if (s.empty()) {
        return sum(0,n-1);
    }
    auto iter=prev(s.end());
    int pr=n;
    while (1) {
        int now=*iter;
        if (mx.first*gop<sum(now,pr-1)*mx.second) { // mx.first/mx.second > y[now]/gop
            mx=P(sum(now,pr-1),gop);
        }
        gop*=x[now];
        if (gop>mod||iter==s.begin()) {
            break;
        }
        pr=now;
        iter--;
    }
	long long vl=mx.first*fastpow(mx.second,mod-2);
	vl%=mod;
	return (all*vl)%mod;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:51:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |         update(i,y[i]);
      |                  ~~~^
horses.cpp:80:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  return (all*val)%mod;
      |         ~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return (all*vl)%mod;
      |         ~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return (all*vl)%mod;
      |         ~~~~~~~~^~~~

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