Submission #1309250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309250		m.zeeshanrashid	Horses (IOI15_horses)	C++20	17 / 100	1597 ms	77240 KiB

horses

// #ifdef __AVX2__
// #pragma GCC target "avx2"
// #endif
// #pragma GCC optimize "O3"
// #pragma GCC optimize "unroll-loops"
#include <bits/stdc++.h>
#include "horses.h"
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds; 
using namespace std;
#define elif else if
#define all(l) begin(l),end(l)
#define rall(l) rbegin(l),rend(l)
#define append push_back
#define print(l) for(auto i:l) cout<<i<<' '; cout<<endl;
#define pprint(a,b) cout<<a<<' '<<b<<endl;
#define inp(l) for(auto &i:l) cin>>i;
// #define ordered_set tree<long long, null_type,less<long long>, rb_tree_tag,tree_order_statistics_node_update>
#define pai make_pair
#define endl "\n"
#define pii pair<long long,long long>
#define fi first
#define se second
#define vec vector

// const long long mod=998244353;
const long long mod1=998244353;
const long long mod=1e9+7;
const long long N=5e5+5;

struct segtree{
	long long size;
	vector<long long>sums,ma;
	void init(long long n){
		size=1;
		while(size<n) size*=2;
		sums.assign(2*size,1);
		ma=sums;
	}
	void set(long long i,long long v,long long x,long long lx,long long rx){
		if(rx-lx==1){
			sums[x]=v;
			ma[x]=v;
			return;
		}
		long long m=(lx+rx)/2;
		if(i<m){
			set(i,v,2*x+1,lx,m);
		}
		else{
			set(i,v,2*x+2,m,rx);
		}
		sums[x]=(sums[2*x+1]*sums[2*x+2])%mod;
		ma[x]=max(ma[2*x+1],ma[2*x+2]);
	}
	void set(long long i, long long v){
		set(i,v,0,0,size);
	}
	long long mul(long long l,long long r,long long x,long long lx,long long rx){
		if(lx>=r or l>=rx) return 1;
		if(lx>=l and rx<=r) return sums[x];
		long long m=(lx+rx)/2;
		long long s1=mul(l,r,2*x+1,lx,m);
		long long s2=mul(l,r,2*x+2,m,rx);
		return (s1*s2)%mod;
	}
	long long mul(long long l,long long r){
		return mul(l,r+1,0,0,size);
	}
	long long mx(long long l,long long r,long long x,long long lx,long long rx){
		if(lx>=r or l>=rx) return -1e18;
		if(lx>=l and rx<=r) return ma[x];
		long long m=(lx+rx)/2;
		long long s1=mx(l,r,2*x+1,lx,m);
		long long s2=mx(l,r,2*x+2,m,rx);
		return max(s1,s2);
	}
	long long mx(long long l,long long r){
		return mx(l,r+1,0,0,size);
	}
	void build(vector<long long>&a,long long x,long long lx,long long rx){
		if(rx-lx==1){
			if(lx<(long long)a.size()){
				sums[x]=a[lx];
			}
			return;
		}
		long long m=(lx+rx)/2;
		build(a,2*x+1,lx,m);
		build(a,2*x+2,m,rx);
		sums[x]=(sums[2*x+1]*sums[2*x+2])%mod;
	}
	void build(vector<long long>&a){
		build(a,0,0,size);
	}
};

vec<long long>x(N,0),y(N,0);
segtree segx,segy;
set<pii>seg;
long long n;

int ans(){
	if(seg.empty())
		return segy.mx(1,n);
	vec<long long>ind,ri;
	long long tem=1;
	for(long long i=0;i<31;i++){
		pii b=*seg.rbegin();
		ind.append(b.fi);
		ri.append(b.se);
		seg.erase(b);
		tem*=x[ind[i]];
		if(tem>1e9 or seg.empty()) break;
	}
	reverse(all(ind));
	reverse(all(ri));
	long long ma=1;
	tem=1;
	for(long long i=0;i<ind.size();i++){
		tem*=x[ind[i]];
		ma=max(ma,tem*segy.mx(ind[i],ri[i]));
		seg.insert(pai(ind[i],ri[i]));
	}
	ma%=mod;
	ma=(ma*segx.mul(1,ind[0]-1))%mod;
	return ma;
}

int updateX(int i,int v){
	i++;
	segx.set(i,v);
	int prev=x[i];
	x[i]=v;
	if(v==1){
		if(prev==1) return ans();
		auto p=seg.lower_bound(pai(i,0));
		pii a=*p;
		if(p!=seg.begin()){
			auto p1=p;
			p1--;
			pii b=*p1;
			seg.erase(b);
			seg.erase(a);
			seg.insert(pai(b.fi,a.se));
		}
		else seg.erase(a);
	}
	else{
		if(prev>1) return ans();
		auto p=seg.lower_bound(pai(i,0));
		if(p!=seg.begin()){
			auto p1=p;
			p1--;
			pii a=(*p1);
			seg.erase(a);
			seg.insert(pai(a.fi,i-1));
			seg.insert(pai(i,a.se));
		}
		else{
			if(seg.empty()) seg.insert(pai(i,n));
			else seg.insert(pai(i,(*seg.begin()).fi-1));
		}
	}
	return ans();
}

int updateY(int i,int v){
	i++;
	segy.set(i,v);
	y[i]=v;
	return ans();
}

long long iter=1,itera=1;
int init(int N, int X[], int Y[]){
	n=N;
	x[n+1]=y[n+1]=1;
	segx.init(n+2);
	for(long long i=1;i<=n;i++){
		long long a=X[i-1];
		x[i]=a;
		segx.set(i,a);
	}
	segy.init(n+2);
	for(long long i=1;i<=n;i++){
		long long b=Y[i-1];
		y[i]=b;
		segy.set(i,b);
	}
	long long st=1,en=1;
	for(long long i=2;i<=n;i++){
		if(x[i]>1){
			seg.insert(pai(st,en));
			st=i;
			en=i;
		}
		else{
			en++;
		}
	}
	seg.insert(pai(st,en));
	if(x[1]==1) seg.erase(seg.begin());
	return ans();
}

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