oj.uz

답안 #81930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81930 2018-10-27T21:44:33 Z GioChkhaidze 말 (IOI15_horses) C++14
0 / 100
 640 ms 25768 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define Mp make_pair
#define F first
#define S second

long long Inf=1000000008,Mod=1000000007;
int n,x[500002],y[500002],ANS;

int v[2000002];
int V[2000002];
int Suf[2000002];
int Pre[2000002];

int L,R,typ;

int Pro(Tree)
{
	if (L>r || l>R) return 1;
	if (L<=l && r<=R) return v[h];
	
	return (1LL*Pro(left)*Pro(right))%Mod;
}

void UpPro(Tree)
{
	if (l>L || r<L) return ;
	if (L==l && r==L) { v[h]=R%Mod; return ; }
	
	UpPro(left);
	UpPro(right);
	
	v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}

void Upd(Tree)
{
	if (L>r || L<l) return ;
	if (L==l && L==r)
	{
		V[h]=L;
		Pre[h]=R;
		Suf[h]=1;
		return ;
	}
	
	Upd(left);
	Upd(right);
		
	if (y[V[2*h]]<1LL*min(Inf,1LL*Suf[2*h]*Pre[2*h+1])*y[V[2*h+1]])
	{
		V[h]=V[2*h+1];
		Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],Inf)*Pre[2*h+1],Inf);
		Suf[h]=Suf[2*h+1];
	}
		else
	{
		V[h]=V[2*h];
		Pre[h]=Pre[2*h];
		Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],Inf)*Suf[2*h],Inf);
	}		
}

pair < int , pair < int , int > > Get(Tree)
{
	if (L>r || l>R) return Mp(0,Mp(1,1));
	if (L<=l && r<=R) return Mp(V[h],Mp(Pre[h],Suf[h]));
	
	pair < int , pair < int , int > > X1=Get(left);
	pair < int , pair < int , int > > X2=Get(right);
	
	if (y[X1.F]<min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,Inf),Inf))
		return Mp(X2.F,Mp(min(1LL*min(1LL*X1.S.F*X1.S.S,Inf)*X2.S.F,Inf),X2.S.S));
	
	if (y[X1.F]>=min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,Inf),Inf))
		return Mp(X1.F,Mp(X1.S.F,min(1LL*min(1LL*X2.S.F*X2.S.S,Inf)*X1.S.S,Inf)));
}

int init(int N, int X[], int Y[]) {

	n=N;
	
	for (int i=1; i<=n; i++)
		x[i]=X[i-1],y[i]=Y[i-1];
	
	for (int i=1; i<=n; i++) {
		L=i; R=x[i]; 
		Upd(1,1,n);
		UpPro(1,1,n);
	}
	
	for (int i=1; i<=n; i++) {
		L=i; R=x[i]; 
		Upd(1,1,n);
	}

	L=1; R=Get(1,1,n).F;

	return (Pro(1,1,n)*y[R])%Mod;
}

int updateX(int pos, int val) {	
	
	pos++;
	
	L=pos; R=val; typ=1;

	x[pos]=val;
			
	Upd(1,1,n);
	UpPro(1,1,n);
	
	L=1; R=Get(1,1,n).F;	
			
	return  (Pro(1,1,n)*y[R])%Mod;
}

int updateY(int pos, int val) {
	
	pos++;
	
	L=pos; R=val; typ=2;
	
	y[pos]=val;
	
	Upd(1,1,n);
	L=1; R=Get(1,1,n).F;	
			
	return  (Pro(1,1,n)*y[R])%Mod;
}

Compilation message

horses.cpp: In function 'int Pro(int, int, int)':
horses.cpp:28:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (1LL*Pro(left)*Pro(right))%Mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void UpPro(int, int, int)':
horses.cpp:34:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if (L==l && r==L) { v[h]=R%Mod; return ; }
                           ~^~~~
horses.cpp:39:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
       ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'void Upd(int, int, int)':
horses.cpp:59:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],Inf)*Pre[2*h+1],Inf);
          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:66:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],Inf)*Suf[2*h],Inf);
          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:105:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (Pro(1,1,n)*y[R])%Mod;
         ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return  (Pro(1,1,n)*y[R])%Mod;
          ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:135:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return  (Pro(1,1,n)*y[R])%Mod;
          ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'std::pair<int, std::pair<int, int> > Get(int, int, int)':
horses.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 460 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 640 ms 25768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 25768 KB Output is correct
2 Incorrect 3 ms 25768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 25768 KB Output is correct
2 Incorrect 2 ms 25768 KB Output isn't correct
3 Halted 0 ms 0 KB -