Submission #387967

#	Time	Username	Problem	Language	Result	Execution time	Memory
387967		nafis_shifat	말 (IOI15_horses)	C++14	17 / 100	306 ms	16976 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;



set<pii> st;

ll x[mxn],y[mxn];
int n;
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 init(int N, int X[], int Y[]) {

	bt.init();
	n = N;

	int last = -1;

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

	if(last != -1) st.insert({last,N - 1});


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


	ll ans = 0;
	ll cm = 0;
	for(int i = N - 1; i >= 0; i--) {
		if(Y[i] > cm) {
			ans = bt.query(i + 1) * Y[i] % mod;
			cm = Y[i] * X[i];
		} else {
			cm = cm * X[i];
		}

		if(cm >= inf) break;
	}

	return ans;
}





ll calc() {
	int k = 0;

	ll ans = 0;
	for(int i = n - 1; i >= 0 && k <= 62; i--,k++) {

		ll v = bt.query(i + 1);
		if(x[i] == 1) {
			auto it = st.lower_bound({i,i});
			if(it->f > i) it--;
			ans = max(ans, v * seg.query(1,1,n,it->f + 1,i + 1));
			i = it->f;
		} else {
			ans = max(ans,v * y[i]);
		}
	}

	return ans;
}

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 && val != 1) {
		auto it = st.lower_bound({pos,pos});
		if(it->f > pos) it--;
		st.erase(it);

		if(it->f != pos) st.insert({it->f,pos - 1});
		if(it->s != pos) st.insert({pos + 1,it->s});

		seg.update(1,1,n,pos + 1,0);
	}
	if(val == 1 && x[pos] != 1) {
		seg.update(1,1,n,pos + 1,y[pos]);
		int l = pos,r = pos;
		if(pos > 0 && x[pos - 1] == 1) {
			auto it = st.lower_bound({pos - 1,pos - 1});
			if(it->f > pos - 1) it--;

			st.erase(it);
			l = it->f;
		}
		if(pos < n - 1 && x[pos + 1] == 1) {
			auto it = st.lower_bound({pos + 1,pos + 1});
			if(it->f > pos + 1) it--;
			st.erase(it);
			r = it->s;
		}

		st.insert({l,r});
	}

	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:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid=b+e>>1;
      |           ~^~
horses.cpp: In member function 'int segtree::query(int, int, int, int, int)':
horses.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=b+e>>1;
      |           ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  117 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:163:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  163 |   seg.update(1,1,n,pos + 1,y[pos]);
      |                            ~~~~~^
horses.cpp:183:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  183 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:189:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  189 |  return calc();
      |         ~~~~^~

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