Submission #747215

#	Time	Username	Problem	Language	Result	Execution time	Memory
747215		Abrar_Al_Samit	Horses (IOI15_horses)	C++17	100 / 100	693 ms	57036 KiB

horses

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

const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
int n;

long long mul(long long a, long long b) {
	return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ret;
}


struct BIT {
	long long b[nax];
	BIT() {
		for(int i=0; i<nax; ++i) {
			b[i] = 1;
		}
	}

	void update(int p, int val) {
		while(p<nax) {
			b[p] = mul(b[p], val);
			p += p&-p;
		}
	}
	long long query(int p) {
		long long ret = 1;
		while(p) {
			ret = mul(ret, b[p]);
			p -= p&-p;
		}
		return ret;
	}

} fen;
int seg[1<<20];
void update(int pos, int val, int l=1, int r=n, int v=1) {
	if(l==r) {
		seg[v] = val;
		return;
	}
	int mid = (l+r)/2;
	if(pos<=mid) update(pos, val, l, mid, v*2);
	else update(pos, val, mid+1, r, v*2+1);
	seg[v] = max(seg[v*2], seg[v*2+1]);
}
int query(int L, int R, int l=1, int r=n, int v=1) {
	if(l>=L && r<=R) return seg[v];
	if(l>R || r<L) return 0;
	int mid = (l+r)/2;
	return max(query(L, R, l, mid, v*2), query(L, R, mid+1, r, v*2+1));
}

set<int>nonone;
int get() {
    long long ret = 0;
    int next_big = n;

    int t = 30;
    long long later = 0;
    for(auto it = prev(nonone.end()); t>0 && later<=MX; --it, --t) {
        long long price = query(*it+1, next_big);
        if(price > later) {
            later = price;

            ret = (price * fen.query(*it+1)) % mod;
        }

        if(it==nonone.begin()) break;
        later *= x[*it];
        next_big = *it;
    }

    return ret;
}
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];
		fen.update(i+1, x[i]);
		update(i+1, y[i]);

		if(x[i]>1) nonone.insert(i);
	}
    nonone.insert(0);
	return get();
}

int updateX(int pos, int val) {	
	fen.update(pos+1, quickpow(x[pos], mod-2));
	fen.update(pos+1, val);

	if(x[pos]==1 && val>1) {
		nonone.insert(pos);
	} else if(x[pos]>1 && val==1) {
		nonone.erase(pos);
	} 

	x[pos] = val;
    nonone.insert(0);

	return get();
}

int updateY(int pos, int val) {
	update(pos+1, val);
	y[pos] = val;

	return get();
}

Compilation message (stderr)

horses.cpp: In function 'int get()':
horses.cpp:87:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |     return ret;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:93:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |   fen.update(i+1, x[i]);
      |                   ~~~^
horses.cpp:94:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |   update(i+1, y[i]);
      |               ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:103:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  fen.update(pos+1, quickpow(x[pos], mod-2));
      |                    ~~~~~~~~^~~~~~~~~~~~~~~

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