Submission #1103674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103674		Pioneer	Horses (IOI15_horses)	C++17	54 / 100	811 ms	68228 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const ll inf=1e9;
const int mod=1e9+7;
const int MAX=5e6+10;

int x[MAX];
int y[MAX];

struct segtree{
	pair<int,bool> t[4*MAX];

	pair<int,bool> mrg(pair<int,bool> a,pair<int,bool> b){
		pair<int,bool> res={(int)(a.first*1ll*b.first%mod),(a.second|b.second)};
		if(a.first*1ll*b.first>=mod){
			res.second=1;
		}
		return res;
	}

	void build(int v,int tl,int tr){
		if(tl==tr){
			t[v]={x[tl],0};
			return;
		}
		int tm=(tl+tr)/2;
		build(2*v,tl,tm);
		build(2*v+1,tm+1,tr);
		t[v]=mrg(t[2*v],t[2*v+1]);
	}

	void update(int v,int tl,int tr,int pos,int x){
		if(tl==tr){
			t[v]={x,0};
			return;
		}
		int tm=(tl+tr)/2;
		if(pos<=tm)update(2*v,tl,tm,pos,x);
		else update(2*v+1,tm+1,tr,pos,x);
		t[v]=mrg(t[2*v],t[2*v+1]);
	}


	pair<int,bool> get(int v,int tl,int tr,int l,int r){
		if(l>r||tl>r||l>tr)return {1,0};
		if(l<=tl&&tr<=r)return t[v];
		int tm=(tl+tr)/2;
		return mrg(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
	}
}tx;


struct segtreeMx{
	pair<int,int> t[MAX];

	pair<int,int> mrg(pair<int,int> a,pair<int,int> b){
		if(a.first>=b.first)return a;
		else return b;
	}

	void build(int v,int tl,int tr){
		if(tl==tr){
			t[v]={y[tl],tl};
			return;
		}
		int tm=(tl+tr)/2;
		build(2*v,tl,tm);
		build(2*v+1,tm+1,tr);
		t[v]=mrg(t[2*v],t[2*v+1]);
	}

	void update(int v,int tl,int tr,int pos,int x){
		if(tl==tr){
			t[v]={x,tl};
			return;
		}
		int tm=(tl+tr)/2;
		if(pos<=tm)update(2*v,tl,tm,pos,x);
		else update(2*v+1,tm+1,tr,pos,x);
		t[v]=mrg(t[2*v],t[2*v+1]);
	}

	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(l>r||tl>r||l>tr)return {0,0};
		if(l<=tl&&tr<=r)return t[v];
		int tm=(tl+tr)/2;
		return mrg(get(2*v,tl,tm,l,r),get(2*v+1,tm+1,tr,l,r));
	}
}ty;

int n;
set<int> st;

int get(int pos){
	int ans=1;
	// for(int i=1;i<=pos;i++)ans=(int)(ans*1ll*x[i]%mod);
	// assert(ans==tx.get(1,1,n,1,pos).first);
	// return ans*1ll*y[pos]%mod;
	return tx.get(1,1,n,1,pos).first*1ll*y[pos]%mod;
}

int get(){
	{
		int pos=n;
		int per=x[n]*1ll*y[n]%mod;
		bool bf=0;
		if(x[n]*1ll*y[n]>=mod)bf=1;
		for(int i=n-1;i>=max(1,n-1000);i--){
			if(!bf&&y[i]>=per){
				pos=i;
				per=y[i];
				bf=0;
			}
			if(per*1ll*x[i]>=mod){
				bf=1;
			}
			per=per*1ll*x[i]%mod;
		}
		return get(pos);
	}
	st.insert(1);
	vector<int> vec;
	int pos=ty.get(1,1,n,*st.rbegin(),n).second;
	vec.push_back(*st.rbegin());
	st.erase(--st.end());
	while(!st.empty()){
		int pos1=ty.get(1,1,n,*st.rbegin(),vec.back()-1).second;
		vec.push_back(*st.rbegin());
		st.erase(--st.end());
		pair<int,bool> bf=tx.get(1,1,n,pos1+1,pos);
		if(bf.second||bf.first*1ll*y[pos]>=mod)break;
		if(bf.first*y[pos]<=y[pos1])pos=pos1;
	}
	for(int x:vec)st.insert(x);
	return get(pos);
}

int init(int N, int X[], int Y[]) {
	// cout<<"! "<<N<<"\n";
	n=N;
	for(int i=0;i<N;i++){
		y[i+1]=Y[i];
		x[i+1]=X[i];
		if(X[i]!=1){
			st.insert(i+1);
		}
	}
	n=N;
	tx.build(1,1,n);
	ty.build(1,1,n);
	return get();
}

int updateX(int pos, int val) {	
	// return 0;
	pos++;
	if(x[pos]!=1)st.erase(pos);
	x[pos]=val;
	tx.update(1,1,n,pos,val);
	if(x[pos]!=1)st.insert(pos);
	return get();
}

int updateY(int pos, int val) {
	// return 0;
	pos++;
	y[pos]=val;
	ty.update(1,1,n,pos,val);
	return get();
}

Compilation message (stderr)

horses.cpp: In member function 'void segtree::update(int, int, int, int, int)':
horses.cpp:36:46: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   36 |  void update(int v,int tl,int tr,int pos,int x){
      |                                          ~~~~^
horses.cpp:11:5: note: shadowed declaration is here
   11 | int x[MAX];
      |     ^
horses.cpp: In member function 'void segtreeMx::update(int, int, int, int, int)':
horses.cpp:76:46: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   76 |  void update(int v,int tl,int tr,int pos,int x){
      |                                          ~~~~^
horses.cpp:11:5: note: shadowed declaration is here
   11 | int x[MAX];
      |     ^
horses.cpp: In function 'int get(int)':
horses.cpp:103:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  return tx.get(1,1,n,1,pos).first*1ll*y[pos]%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:99:6: warning: unused variable 'ans' [-Wunused-variable]
   99 |  int ans=1;
      |      ^~~
horses.cpp: In function 'int get()':
horses.cpp:109:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |   int per=x[n]*1ll*y[n]%mod;
      |           ~~~~~~~~~~~~~^~~~
horses.cpp:121:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |    per=per*1ll*x[i]%mod;
      |        ~~~~~~~~~~~~^~~~
horses.cpp:138:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  138 |  for(int x:vec)st.insert(x);
      |          ^
horses.cpp:11:5: note: shadowed declaration is here
   11 | int x[MAX];
      |     ^

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