Submission #202409

#	Time	Username	Problem	Language	Result	Execution time	Memory
202409		anonymous	Horses (IOI15_horses)	C++14	17 / 100	88 ms	49724 KiB

horses

#include "horses.h"
#include<iostream>
#define MOD 1000000007
#define LL long long
#define INF (1LL<<30)
#define MAXN 500005
using namespace std;
LL n, x[MAXN], y[MAXN];
class Segtree {
    LL ST[MAXN*4][4]; //mod product, actual (or inf), opt product, opt
public:
    void pushup(int cur) {
        ST[cur][0]=(ST[2*cur][0]*ST[2*cur+1][0])%MOD;
        ST[cur][1]=min(ST[2*cur][1]*ST[2*cur+1][1], INF);
        if (ST[2*cur][1] == INF || ST[2*cur][2] <= ST[2*cur+1][2]*ST[2*cur][1]) {
            ST[cur][2] = min(ST[2*cur+1][2]*ST[2*cur][1], INF);
            ST[cur][3] = ST[2*cur+1][3];
        } else {
            ST[cur][2] = ST[2*cur][2];
            ST[cur][3] = ST[2*cur][3];
        }
    }
    void build(int l, int r, int cur) {
        if (l == r) {
            ST[cur][0] = x[l];
            ST[cur][1] = x[l];
            ST[cur][2] = min(x[l]*y[l], INF);
            ST[cur][3] = l;
        } else {
            int mid=(l+r)>>1;
            build(l, mid, 2*cur);
            build(mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    void upd(int ind, int l, int r, int cur) {
        if (l > ind || r < ind) {return;}
        if (l == r) {
            ST[cur][0] = x[l];
            ST[cur][1] = x[l];
            ST[cur][2] = min(x[l]*y[l], INF);
            ST[cur][3] = l;
        } else {
            int mid=(l+r)>>1;
            upd(ind, l, mid, 2*cur);
            upd(ind, mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    LL ask(int ind, int l, int r, int cur) { //ask for prefix mod product
        if (ind < l) {return(1);}
        if (r <= ind) {return(ST[cur][0]);}
        else {
            int mid=(l+r)>>1;
            return((ask(ind, l, mid, 2*cur)*ask(ind, mid+1, r, 2*cur+1))%MOD);
        }
    }
    LL opt() {return(ST[1][3]);}
} ST;

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];
	}
	ST.build(0, N-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0, N-1, 1);
	return((prod * y[p])%MOD);
}

int updateX(int pos, int val) {
	x[pos]=val;
	ST.upd(pos, 0, n-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0,n-1, 1);
	return((prod * y[p])%MOD);
}

int updateY(int pos, int val) {
	y[pos]=val;
	ST.upd(pos, 0, n-1, 1);
	LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
	return((prod * y[p])%MOD);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:68:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, N-1, 1);
                                             ^
horses.cpp:69:22: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return((prod * y[p])%MOD);
        ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:74:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ST.upd(pos, 0, n-1, 1);
                 ~^~
horses.cpp:75:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0,n-1, 1);
                                            ^
horses.cpp:75:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0,n-1, 1);
                                      ~^~
horses.cpp:76:22: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return((prod * y[p])%MOD);
        ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:81:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ST.upd(pos, 0, n-1, 1);
                 ~^~
horses.cpp:82:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                             ^
horses.cpp:82:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  LL p = ST.opt(), prod = ST.ask(p, 0, n-1, 1);
                                       ~^~
horses.cpp:83:22: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return((prod * y[p])%MOD);
        ~~~~~~~~~~~~~~^~~~~

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