Submission #388282

#	Time	Username	Problem	Language	Result	Execution time	Memory
388282		nafis_shifat	Horses (IOI15_horses)	C++14	37 / 100	332 ms	40388 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e9;
const ll mod = 1e9 + 7;


ll x[mxn],y[mxn];
int n;


set<int> st;



ll bigmod(ll a,ll b) {
	if(b==0)return 1;
	ll mid=b/2;
	ll c=bigmod(a,mid);
	if(b%2==0)return (c*c)%mod;
	c=(c*c)%mod;
	return (a*c)%mod;
}



struct segtree {
	int tree[4*mxn] = {};
 
	void update(int node,int b,int e,int p,int v) {
		if(e<p|| b>p)return;
		if(b == e) {
			tree[node] = v;
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
 
		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node]=max(tree[left],tree[right]);
	}
 
	int query(int node,int b,int e,int l,int r) {
		if(e<l || b>r) return 0;
		if(b>=l && e<=r) {
			return tree[node];
		}
		
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		return max(query(left,b,mid,l,r),query(right,mid + 1, e, l,r));
	}
} seg;





struct BIT
{
	ll bit[mxn];
	void init() {
		for(int i = 1; i < mxn; i++) bit[i] = 1;
	}	

	void update(int p,ll v) {
		if(p==0) return;
		for(;p<mxn;p+=p&-p) bit[p] = bit[p] * v % mod;
	}
    ll query(int p) {
    	ll r = 1;
    	for(;p>0;p-=p&-p) r = bit[p] * r % mod;
        return r;
    }
} bt;


int calc() {



	if(st.empty()) {
		return seg.query(1,1,n,1,n);
	}
	int k = 0;

	ll ans = 0;
	ll cm = 0;

	int last = n;
	for(auto it = st.rbegin(); it != st.rend() && k <= 62; it++,k++) {
		int i = *it;
		if(last - i > 1) {
			ll v1 = bt.query(i + 2);
			ll v2 = seg.query(1,1,n, i + 2, last);

			if(v2 > cm) {
				ans = v1 * v2 % mod;
				cm = v2;
			}
		}
		last = i;
		ll v1 = bt.query(i + 1);
		ll v2 = y[i];
		if(v2 > cm) {
			ans = v1 * v2 % mod;
			cm = x[i] * v2;
		} else {
			cm = cm * x[i];
		}

		if(cm >= inf) break;
	}

	return ans;
}



int init(int N, int X[], int Y[]) {


	for(int i = 0; i < N; i++) {
		x[i] = X[i];
		y[i] = Y[i];
		if(X[i] != 1) st.insert(i);
		else {
			seg.update(1,1,N,i + 1,y[i]);
		}
	}

	bt.init();
	n = N;

	
	for(int i = 1; i <= N; i++) {
		bt.update(i,X[i - 1]);
	}
	return calc();
}




int updateX(int pos, int val) {	

	ll tv = bigmod(x[pos],mod - 2);
	bt.update(pos + 1, tv);
	bt.update(pos + 1,val);
	if(x[pos] == 1) {
		st.erase(pos);
		seg.update(1,1,n,pos + 1,0);
	}
	if(val == 1) {
		st.insert(pos);
		seg.update(1,1,n,pos + 1,y[pos]);
	}
	x[pos] = val;
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	if(x[pos] == 1) {
		seg.update(1,1,n,pos + 1,val);
	}
	return calc();
}

Compilation message (stderr)

horses.cpp: In member function 'void segtree::update(int, int, int, int, int)':
horses.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid=b+e>>1;
      |           ~^~
horses.cpp: In member function 'int segtree::query(int, int, int, int, int)':
horses.cpp:56:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid=b+e>>1;
      |           ~^~
horses.cpp: In function 'int calc()':
horses.cpp:123:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  return ans;
      |         ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:136:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  136 |    seg.update(1,1,N,i + 1,y[i]);
      |                           ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:164:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  164 |   seg.update(1,1,n,pos + 1,y[pos]);
      |                            ~~~~~^

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