Submission #235195

#	Time	Username	Problem	Language	Result	Execution time	Memory
235195		anubhavdhar	Horses (IOI15_horses)	C++14	0 / 100	567 ms	80048 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;
/*
const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 5e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/

#define MAXN 500005
#define MOD 1000000007

ll fxp(ll a, ll n)
{
	if(n == 0)
		return 1;
	if(n&1)
		return (a*fxp(a, n-1))%MOD;
	ll val = fxp(a, n<<1);
	return (val * val)%MOD;
}

#define inv(a) fxp(a, MOD - 2);

ll x[MAXN], y[MAXN], prod, N, invX[MAXN];

set<ii> S;

struct Segtree_aux
{
	ll st[4*MAXN], st_max[4*MAXN], sum[4*MAXN];
 
	void upd(int node, int ss, int se, int i, ll val)
	{
		if(ss > i or se < i)
			return;
		if(ss == se)
		{
			st[node] = val % MOD;
			st_max[node] = val * y[i]; 
			sum[node] = val;
			return;
		}
		int mid = (ss + se)/2;
		upd(node*2+1, ss, mid, i, val);
		upd(node*2+2, mid + 1, se, i, val);
		st[node] = (st[node*2+1] * st[node*2+2]) % MOD;
		if(sum[node*2+1] > 1000000000 and sum[node*2+2] > 1000000000)
			sum[node] = -1;
		else
			sum[node] = sum[node*2+1] * sum[node*2+2];
		st_max[node] = max(st_max[node*2 + 1], sum[node*2+1] * st_max[node*2 + 2]);
	}
 
	ll quer(int node, int ss, int se, int l, int r)
	{
		if(ss > r or se < l)
			return 1;
		if(ss >= l and se <= r)
			return st[node];
		int mid = (ss + se)/2;
		return (quer(node*2+1, ss, mid, l, r) * quer(node*2+2, mid + 1, se, l, r)) % MOD;
	}

	ll quer2(int node, int ss, int se, int p)
	{
		// cout<<"asking for ["<<ss<<','<<se<<"] for "<<p<<", having value "<<st_max[node]<<"\n";
		if(se < p)
			return 0;
		if(ss == se)
			return ss;
		int mid = (ss + se)/2;
		if( (mid < p or st_max[node] == st_max[node*2+2] * sum[node*2+1]) && se < N)
			return quer2(node*2 + 2, mid + 1, se, p);
		return quer2(node*2 + 1, ss, mid, p);
	}
 
	Segtree_aux()
	{
		F0R(i, 4*MAXN)
			st[i] = 1;
	}
 
	inline void update(int i, ll val)
	{
		upd(0, 0, MAXN, i, val);
	}
 
	inline ll query(int i)
	{
		return quer(0, 0, MAXN, 0, i);
	}

	inline ll query2(int i)
	{
		return quer2(0, 0, MAXN, i);
	}
} aux;

int updateX(int i, int val)
{
	aux.update(i, val);
	S.erase(mp(-i, x[i]));
	prod = (((prod * invX[i])%MOD)*val)%MOD;
	x[i] = val;
	invX[i] = inv(val);
	if(x[i] != 1)
		S.insert(mp(-i, x[i]));
	int ind = N-1;
	ll tmpProd = 1;
	for(ii pp : S)
	{
		tmpProd *= x[-pp.ff];
		ind = -pp.ff; 
		if(tmpProd > 1000000000)
			break;
	}
	ind = aux.query2(ind);
	// cout<<"index found is "<<ind<<endl;
	return (y[ind] * aux.query(ind))%MOD;
}

int updateY(int pos, int val)
{
	y[pos] = val;
	aux.update(pos, x[pos]);
	int ind = N-1;
	ll tmpProd = 1;
	for(ii pp : S)
	{
		tmpProd *= x[-pp.ff];
		if(tmpProd > 1000000000)
			break;
		ind = -pp.ff; 
	}
	ind = aux.query2(ind);
	// cout<<"index found is "<<ind<<endl;
	return (y[ind] * aux.query(ind))%MOD;
}

int init(int n, int* X, int* Y)
{
	N = n;
	// ll amt = 0;
	prod = 1;
	// F0R(i, N)
	// {
	// 	x[i] = X[i];
	// 	y[i] = Y[i];
	// 	S.update(i, MAXN, log2(x[i]));
	// 	S.update(i, i, log2(y[i]));
	// 	aux.update(i, X[i]);
	// 	prod *= X[i];
	// 	amt = max(amt, prod*Y[i]);
	// }
	S.insert(mp(0, 100000000000));
	F0R(i, N)
	{
		x[i] = X[i];
		y[i] = Y[i];
		invX[i] = inv(X[i]);
		S.insert(mp(-i, x[i]));
		prod = (prod * x[i])%MOD;
		aux.update(i, x[i]);
	}
	return updateX(0, x[0]);
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	int N, X[120], Y[120], M, j, i, k;
	cin>>N;
	FOR(i, N)
		cin>>X[i];
	FOR(i, N)	
		cin>>Y[i];
	cout<<init(N, X, Y)<<endl;
	cin>>M;
	FOR(i, M)
	{
		char c;
		cin>>c>>j>>k;
		if(c == 'X')
			cout<<updateX(j, k)<<endl;
		else
			cout<<updateY(j, k)<<endl;
	}
	return 0;
}*/

Compilation message (stderr)

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:139:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  int ind = N-1;
            ~^~
horses.cpp:144:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   ind = -pp.ff; 
         ^
horses.cpp:148:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ind = aux.query2(ind);
        ~~~~~~~~~~^~~~~
horses.cpp:150:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (y[ind] * aux.query(ind))%MOD;
                                  ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:157:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  int ind = N-1;
            ~^~
horses.cpp:164:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   ind = -pp.ff; 
         ^
horses.cpp:166:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ind = aux.query2(ind);
        ~~~~~~~~~~^~~~~
horses.cpp:168:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (y[ind] * aux.query(ind))%MOD;
                                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:196:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return updateX(0, x[0]);
                    ~~~^

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