Submission #140754

#	Time	Username	Problem	Language	Result	Execution time	Memory
140754		babo	Horses (IOI15_horses)	C++14	0 / 100	1551 ms	87136 KiB

horses

#include <bits/stdc++.h>
#define mod 1000000007
#define L long long

using namespace std;

L n,allmul=1;
set<L>st;
L x[500050],y[500050];
L matr[2000020],multr[2000020];

L po(L x,L y){
	if(y==0) return 1;
	L temp=po(x,y/2);
	if(y%2) return temp*temp%mod*x%mod;
	else return temp*temp%mod;
}

L inv(L x){
	return po(x,mod-2);
}

void mulup(L now,L S,L E,L loc,L val){
	if(loc>E||loc<S) return;
	multr[now]=multr[now]*val%mod;
	if(S==E)
		return;
	L mid=(S+E)/2;
	mulup(now*2,S,mid,loc,val);
	mulup(now*2+1,mid+1,E,loc,val);
}
L mulget(L now,L S,L E,L s,L e){
	if(s>E||e<S) return 1;
	if(s<=S&&E<=e) return multr[now];
	L mid=(S+E)/2;
	return mulget(now*2,S,mid,s,e)*mulget(now*2+1,mid+1,E,s,e)%mod;
}
void maup(L now,L S,L E,L loc,L val){
	if(loc>E||loc<S) return;
	if(S==E)
	{
		matr[now]=val;
		return;
	}
	L mid=(S+E)/2;
	maup(now*2,S,mid,loc,val);
	maup(now*2+1,mid+1,E,loc,val);
	matr[now]=max(matr[now*2],matr[now*2+1]);
}
L maget(L now,L S,L E,L s,L e){
	if(s>E||e<S) return 0;
	if(s<=S&&E<=e) return matr[now];
	L mid=(S+E)/2;
	return max(maget(now*2,S,mid,s,e),maget(now*2+1,mid+1,E,s,e));
}


L solve(){
	L i,ret=0,multemp=allmul;
	set<L>::iterator it=st.end();
	it--;it--;
	for(i=0;i<30&&it!=st.begin();i++)
	{
		multemp=multemp*inv(x[*it])%mod;
		it--;
	}
	printf("%lld\n",multemp);
	L multemp2=1;
	while(next(it)!=st.end())
	{
		L lef=*it,rig=*next(it);
		printf("%lld %lld %lld %lld\n",lef,rig,multemp2,maget(1,1,500000,lef,rig-1)%mod);
		ret=max(ret,multemp2*maget(1,1,500000,lef,rig-1)%mod);
		multemp2=multemp2*x[*it]%mod;
		it++;
	}
	return ret*multemp%mod;
}

L init(int N,int X[],int Y[]){
	n=(L)N;
	L i;
	for(i=0;i<n;i++)
	{
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	for(i=1;i<2000020;i++)
		multr[i]=1;
	for(i=1;i<=n;i++)
	{
		allmul=allmul*x[i]%mod;
		mulup(1,1,500000,i,x[i]);
		maup(1,1,500000,i,y[i]);
		if(x[i]!=1)
			st.insert(i);
	}
	st.insert(n+1);
	st.insert(1);
	return solve();
}

L updateX(int pos,int val){
	pos++;
	allmul=allmul*inv(x[pos])%mod*val%mod;
	if(pos!=1&&x[pos]==1) st.erase((L)pos);
	if(val==1) st.insert((L)pos);
	mulup(1,1,500000,(L)pos,inv(x[pos]));
	mulup(1,1,500000,(L)pos,(L)val);
	x[pos]=val;
	return solve();
}
L updateY(int pos,int val){
	pos++;
	maup(1,1,500000,(L)pos,(L)val);
	return solve();
}
/*
#include <stdio.h>
#include <stdlib.h>

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}


int main() {
	_inputFile = fopen("input.txt", "rb");
	_outputFile = fopen("output.txt", "w");
	
	int N; N = _readInt();

	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

	for (int i = 0; i < N; i++) {
		X[i] = _readInt();
	}

	for (int i = 0; i < N; i++) {
		Y[i] = _readInt();
	}	

	fprintf(_outputFile,"%d\n",init(N,X,Y));

	int M; M = _readInt();

	for (int i = 0; i < M; i++) {
		int type; type = _readInt();
		int pos; pos = _readInt();
		int val; val = _readInt(); 

		if (type == 1) {
			fprintf(_outputFile,"%d\n",updateX(pos,val));
		} else if (type == 2) {
			fprintf(_outputFile,"%d\n",updateY(pos,val));
		}
	}

	return 0;
}
*/

Compilation message (stderr)

horses.cpp: In function 'long long int po(long long int, long long int)':
horses.cpp:12:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 L po(L x,L y){
             ^
horses.cpp:9:13: note: shadowed declaration is here
 L x[500050],y[500050];
             ^
horses.cpp:12:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 L po(L x,L y){
             ^
horses.cpp:9:3: note: shadowed declaration is here
 L x[500050],y[500050];
   ^
horses.cpp: In function 'long long int inv(long long int)':
horses.cpp:19:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 L inv(L x){
          ^
horses.cpp:9:3: note: shadowed declaration is here
 L x[500050],y[500050];
   ^

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