Submission #235112

#	Time	Username	Problem	Language	Result	Execution time	Memory
235112		anubhavdhar	Horses (IOI15_horses)	C++14	54 / 100	1033 ms	91040 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 MOD 1000000007
#define MAXN 500005
#define log2 111*log2
int x[MAXN], y[MAXN];
 
struct Segtree_aux
{
	ll st[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;
			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;
	}
 
	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;
	}
 
	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);
	}
} aux;
 
struct Segtree_main
{
	ldd st[4*MAXN], lz[4*MAXN];
 
	inline void push(int node, int ss, int se)
	{
		if(lz[node] == 0)
			return;
		// else
			// cout<<"lz["<<ss<<','<<se<<"] = "<<lz[node]<<'\n';
		st[node] += lz[node];
		// cout<<"["<<ss<<","<<se<<"] = "<<st[node]<<" now\n";
		if(ss != se)
		{
			lz[node*2+1] += lz[node];
			lz[node*2+2] += lz[node];
		}
		lz[node] = 0;
	}
 
	void upd(int node, int ss, int se, int l, int r, ldd val)
	{
		push(node, ss, se);
		if(ss > r or se < l)
			return;
		if(ss >= l and se <= r)
		{
			lz[node] += val;
			// cout<<"added "<<val<<" to the entire range ["<<ss<<","<<se<<"] \n";
			push(node, ss, se);
			return;
		}
		int mid = (ss + se)/2;
		upd(node*2+1, ss, mid, l, r, val);
		upd(node*2+2, mid + 1, se, l, r, val);
		st[node] = max(st[node*2+1], st[node*2+2]);
		// cout<<"updated ["<<ss<<','<< se<<"] to "<<st[node]<<'\n';
	}
 
	int quer(int node, int ss, int se)
	{
		// cout<<"Asking ["<<ss<<' '<<se<<"] -> "<<st[node]<<'\n';
		// push(node, ss, se);
		if(ss == se)
			return ss;
		int mid = (ss + se)/2;
		push(node*2+1, ss, mid);
		if(st[node*2+1] == st[node])
			return quer(node*2+1, ss, mid);
		push(node*2+2,mid +1, se);
		return quer(node*2+2, mid + 1, se);
	}
 
	Segtree_main()
	{
		F0R(i, 4*MAXN)
			st[i] = lz[i] = 0;
	}
 
	inline void update(int l, int r, ldd val)
	{
		// cout<<"asked for update("<<l<<','<<r<<','<<val<<")\n";
		upd(0, 0, MAXN, l, r, val);
	}
 
	inline int query()
	{
		push(0, 0, MAXN); 
		int i = quer(0, 0, MAXN);
		// cout<<"index found is "<<i<<'\n';
		ll p = aux.query(i) * y[i];
      	p %= MOD;
		return p;
	}
 
} S;
 
 
 
int updateX(int pos, int val)
{
	aux.update(pos, (ll)val);
	S.update(pos, MAXN, log2(val) - log2(x[pos]));
	x[pos] = val;
	return S.query();
}
 
int updateY(int pos, int val)
{
	// aux.update(pos, val);
	S.update(pos, pos, log2(val) - log2(y[pos]));
	y[pos] = val;
	return S.query();
}
 
int init(int N, int* X, int* Y)
{
	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]);
	}
	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 member function 'int Segtree_main::query()':
horses.cpp:162:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return p;
          ^

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