Submission #512595

#	Time	Username	Problem	Language	Result	Execution time	Memory
512595		AdamGS	말 (IOI15_horses)	C++17	100 / 100	366 ms	49112 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
const ll MOD=1e9+7;
set<pair<ll,ll>>S;
ll ilo[4*LIM], ilomod[4*LIM], tr[4*LIM], N=1, n;
ll cntilo(int l, int r) {
	l+=N; r+=N;
	ll ans=ilo[l];
	if(l!=r) ans=min(ans*ilo[r], MOD);
	while(l/2!=r/2) {
		if(l%2==0) ans=min(ans*ilo[l+1], MOD);
		if(r%2==1) ans=min(ans*ilo[r-1], MOD);
		l/=2; r/=2;
	}
	return ans;
}
ll cntma(int l, int r) {
	l+=N; r+=N;
	ll ans=max(tr[l], tr[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, tr[l+1]);
		if(r%2==1) ans=max(ans, tr[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
ll cntmod(int l, int r) {
	if(r<l) return 1;
	l+=N; r+=N;
	ll ans=ilomod[l];
	if(l!=r) ans=(ans*ilomod[r])%MOD;
	while(l/2!=r/2) {
		if(l%2==0) ans=(ans*ilomod[l+1])%MOD;
		if(r%2==1) ans=(ans*ilomod[r-1])%MOD;
		l/=2; r/=2;
	}
	return ans;
}
ll solve() {
	int p=0, k=n-1;
	while(p<k) {
		int sr=(p+k)/2;
		if(cntilo(sr, n-1)==MOD) p=sr+1; else k=sr;
	}
	ll ans=0, akt=1;
	if(k) ans=tr[N+k-1];
	while(k<n) {
		akt*=ilo[k+N];
		auto it=S.upper_bound({k, -MOD});
		auto a=*it;
		if(a.st>k+1) a={k, k};
		else a={k, a.nd};
		ans=max(ans, akt*cntma(a.st, a.nd));
		k=a.nd+1;
	}
	ans%=MOD;
	ans=(ans*cntmod(0, p-1))%MOD;
	return ans;
}
int init(int D, int X[], int Y[]) {
	n=D;
	while(N<n) N*=2;
	rep(i, 2*N) ilo[i]=ilomod[i]=1;
	rep(i, n) {
		ilo[N+i]=ilomod[N+i]=X[i];
		tr[N+i]=Y[i];
	}
	for(int i=N-1; i; --i) {
		ilo[i]=min(ilo[2*i]*ilo[2*i+1], MOD);
		ilomod[i]=(ilomod[2*i]*ilomod[2*i+1])%MOD;
		tr[i]=max(tr[2*i], tr[2*i+1]);
	}
	S.insert({-MOD, -MOD});
	S.insert({MOD, MOD});
	int p=0;
	rep(i, n) {
		if(X[i]!=1) {
			if(p!=i) S.insert({p, i-1});
			p=i+1;
		}
	}
	if(p!=n) S.insert({p, n-1});
	return solve();
}
int updateX(int v, int x) {	
	if(ilo[v+N]==1) {
		auto it=S.upper_bound({v, MOD+1}); --it;
		auto p=*it;
		if(p.nd==v) {
			S.erase(it);
			if(p.st!=p.nd) S.insert({p.st, p.nd-1});
		} else if(p.st==v) {
			S.erase(it);
			S.insert({p.st+1, p.nd});
		} else {
			S.erase(it);
			S.insert({p.st, v-1});
			S.insert({v+1, p.nd});
		}
	}
	if(x==1) {
		auto it=S.upper_bound({v, v});
		auto it2=it; --it2;
		auto a=*it2, b=*it;
		if(a.nd==v-1 && b.st==v+1) {
			S.erase(it2);
			it=S.upper_bound({v, v});
			S.erase(it);
			S.insert({a.st, b.nd});
		} else if(a.nd==v-1) {
			S.erase(it2);
			S.insert({a.st, v});
		} else if(b.st==v+1) {
			S.erase(it);
			S.insert({v, b.nd});
		} else S.insert({v, v});
	}
	v+=N;
	ilo[v]=ilomod[v]=x;
	v/=2;
	while(v) {
		ilo[v]=min(ilo[2*v]*ilo[2*v+1], MOD);
		ilomod[v]=(ilomod[2*v]*ilomod[2*v+1])%MOD;
		v/=2;
	}
	return solve();
}
int updateY(int v, int x) {
	v+=N;
	tr[v]=x;
	v/=2;
	while(v) {
		tr[v]=max(tr[2*v], tr[2*v+1]);
		v/=2;
	}
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'll cntilo(int, int)':
horses.cpp:16:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   16 |  l+=N; r+=N;
      |  ~^~~
horses.cpp:16:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   16 |  l+=N; r+=N;
      |        ~^~~
horses.cpp: In function 'll cntma(int, int)':
horses.cpp:27:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |  l+=N; r+=N;
      |  ~^~~
horses.cpp:27:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |  l+=N; r+=N;
      |        ~^~~
horses.cpp: In function 'll cntmod(int, int)':
horses.cpp:38:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |  l+=N; r+=N;
      |  ~^~~
horses.cpp:38:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |  l+=N; r+=N;
      |        ~^~~
horses.cpp: In function 'll solve()':
horses.cpp:49:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   49 |  int p=0, k=n-1;
      |             ~^~
horses.cpp:52:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |   if(cntilo(sr, n-1)==MOD) p=sr+1; else k=sr;
      |                 ~^~
horses.cpp:7:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | #define st first
      |            ^
horses.cpp:62:28: note: in expansion of macro 'st'
   62 |   ans=max(ans, akt*cntma(a.st, a.nd));
      |                            ^~
horses.cpp:8:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    8 | #define nd second
      |            ^
horses.cpp:62:34: note: in expansion of macro 'nd'
   62 |   ans=max(ans, akt*cntma(a.st, a.nd));
      |                                  ^~
horses.cpp:63:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |   k=a.nd+1;
      |     ~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   77 |  for(int i=N-1; i; --i) {
      |            ~^~
horses.cpp:92:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   92 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:127:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |  v+=N;
      |  ~^~~
horses.cpp:135:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  135 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:3: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |  v+=N;
      |  ~^~~
horses.cpp:145:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  145 |  return solve();
      |         ~~~~~^~

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