Submission #658379

#	Time	Username	Problem	Language	Result	Execution time	Memory
658379		jamezzz	Horses (IOI15_horses)	C++17	80 / 100	1519 ms	217516 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
#define mod 1000000007

struct node{
	int s,e,m;ll v=1,lz=1;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		v=(v*lz)%mod;
		if(s!=e){
			l->lz=(lz*l->lz)%mod;
			r->lz=(lz*r->lz)%mod;
		}
		lz=1;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){lz=(lz*nv)%mod;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		v=max(l->v,r->v);
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
	void print(){
		printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
		if(s!=e)l->print(),r->print();
	}
}*rt;

struct node2{
	int s,e,m;ll v=1,lz=1;
	node2 *l,*r;
	node2(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1;
		if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
	}
	void ppo(){
		v=(v*lz)%mod;
		if(s!=e){
			l->lz=(lz*l->lz)%mod;
			r->lz=(lz*r->lz)%mod;
		}
		lz=1;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){lz=(lz*nv)%mod;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo(),r->ppo();
		v=(l->v*r->v)%mod;
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return (l->qry(x,m)*r->qry(m+1,y))%mod;
	}
	void print(){
		printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
		if(s!=e)l->print(),r->print();
	}
}*pfx;

struct node3{
	int s,e,m,v;
	node3 *l,*r;
	node3(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,v=0;
		if(s!=e)l=new node3(s,m),r=new node3(m+1,e);
	}
	void up(int x,ll nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	ll qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
	void print(){
		printf("%d %d %d %lld\n",s,e,m,v);
		if(s!=e)l->print(),r->print();
	}
}*yrt;

ll fp(ll x,int a){
	if(a==0)return 1;
	ll t=fp(x,a/2);
	ll r=(t*t)%mod;
	if(a%2)r=(r*x)%mod;
	return r;
}

#define maxn 500005
int n,x[maxn],y[maxn];
set<ii> s;

int ans(){
	auto it=s.end();
	ll mx=1;
	int pv=n;
	while(it!=s.begin()){
		--it;
		auto[i,x]=*it;
		//check if [i,n-1] can be >1e9
		mx=max(mx,yrt->qry(i,pv-1));
		mx*=x;
		if(mx>1e9){
			if(i==0)return mx%mod;
			ll f=pfx->qry(0,i-1);
			return (f*(mx%mod))%mod;
		}
		pv=i;
	}
	return rt->qry(0,n-1);
}

int init(int N,int X[],int Y[]){
	n=N;
	rt=new node(0,n-1);
	pfx=new node2(0,n-1);
	yrt=new node3(0,n-1);
	for(int i=0;i<n;++i){
		x[i]=X[i],y[i]=Y[i];
		rt->up(i,n-1,x[i]);
		pfx->up(i,i,x[i]);
		rt->up(i,i,y[i]);
		yrt->up(i,y[i]);
		if(x[i]!=1)s.insert({i,x[i]});
	}
	return ans();
}

int updateX(int pos,int val){	
	if(x[pos]!=1)s.erase({pos,x[pos]});
	rt->up(pos,n-1,fp(x[pos],mod-2));
	pfx->up(pos,pos,fp(x[pos],mod-2));
	rt->up(pos,n-1,val);
	pfx->up(pos,pos,val);
	x[pos]=val;
	if(val!=1)s.insert({pos,val});
	return ans();
}

int updateY(int pos,int val){
	rt->up(pos,pos,fp(y[pos],mod-2));
	rt->up(pos,pos,val);
	yrt->up(pos,val);
	y[pos]=val;
	return ans();
}

Compilation message (stderr)

horses.cpp: In member function 'void node3::up(int, ll)':
horses.cpp:91:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   if(s==x&&e==x){v=nv;return;}
      |                    ^~
horses.cpp: In member function 'void node3::print()':
horses.cpp:103:23: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int' [-Wformat=]
  103 |   printf("%d %d %d %lld\n",s,e,m,v);
      |                    ~~~^          ~
      |                       |          |
      |                       |          int
      |                       long long int
      |                    %d
horses.cpp: In function 'int ans()':
horses.cpp:126:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  126 |   auto[i,x]=*it;
      |          ^
horses.cpp:117:7: note: shadowed declaration is here
  117 | int n,x[maxn],y[maxn];
      |       ^
horses.cpp:130:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  130 |   if(mx>1e9){
      |      ^~
horses.cpp:131:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  131 |    if(i==0)return mx%mod;
      |                     ^
horses.cpp:133:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |    return (f*(mx%mod))%mod;
      |                       ^
horses.cpp:137:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |  return rt->qry(0,n-1);
      |         ~~~~~~~^~~~~~~

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