제출 #1365897

#제출 시각아이디문제언어결과실행 시간메모리
1365897stanirina말 (IOI15_horses)C++20
컴파일 에러
0 ms0 KiB
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;
int MOD=1e9+9;
set<int> s; ///skup pozicija koje nisu 1
vector<ll> sty; /// seg tree za maks za y, ali obrnut
int szy;
vector<ll> stx; /// seg tree za proizvod, ali obrnut
int szx;
vector<ll> x,y;

int stepen(int n){
	int i=0;
	while(1<<i < n)i++;
	return (1<<i);
}

void postaviy (ll val, int pos){
	pos+=szy;
	sty[pos]=val;
	pos/=2;
	while(pos>=1){
		sty[pos]=max(sty[pos*2],sty[pos*2+1]);
		pos/=2;
	}
}

ll gety (int l, int r){
	l+=szy;
	r+=szy;
	int ans=0ll;
	while(l<=r){
		if(l%2==1)ans=max(ans,sty[l++]);
		if(r%2==0)ans=max(ans,sty[r--]);
		l/=2;
		r/=2;
	}
	return ans;
}

void postavix (ll val, int pos){
	pos+=szx;
	stx[pos]=val;
	pos/=2;
	while(pos>=1){
		stx[pos]=(stx[pos*2]*stx[pos*2+1])%MOD;;
		pos/=2;
	}
}

ll getx (int l, int r){
	l+=szx;
	r+=szx;
	ll ans=1ll;
	while(l<=r){
		if(l%2==1)ans=(ans*stx[l++])%MOD;
		if(r%2==0)ans=(ans*stx[r--])%MOD;
		l/=2;
		r/=2;
	}
	return (ans%MOD);
}

ll resi(){
	ll ans=1ll;
	int cur=0;
	for(auto a:s){
		if(ans>MOD){
			ans%=MOD;
			break;
		}
		ans=(x[n-a-1]*max(ans,gety(cur,a)))%MOD;
		cur=a;
	}
	ans=(ans*getx(a+1,n-1))%MOD;
	return ans;
}

int init(int N, int X[], int Y[]) {
	n=N;
	x.resize(n);
	for(int i=0;i<n;i++)x[i]=(ll)X[i];
	y.resize(n);
	for(int i=0;i<n;i++)y[i]=(ll)Y[i];
	
	for(int i=0;i<n;i++){
		if(X[i]!=1)s.insert(n-i-1);
	}
	szy=stepen(n);
	sty.assign(2*szy,0ll);
	for(int i=0;i<n;i++)postaviy((ll)Y[i],n-i-1);
	
	szx=stepen(n);
	stx.assign(2*szx,1ll);
	for(int i=0;i<n;i++)postavix((ll)X[i],n-i-1);
	
	return (int)resi();
}

int updateX(int pos, int val) {	
	if(x[pos]!=1ll)s.erase(n-pos-1);
	postavix((ll)val, n-pos-1);
	if(val!=1)s.insert(n-pos-1);
	
	return resi();
}

int updateY(int pos, int val) {
	postaviy((ll)val,n-pos-1);
	return resi();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'll gety(int, int)':
horses.cpp:37:34: error: no matching function for call to 'max(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
   37 |                 if(l%2==1)ans=max(ans,sty[l++]);
      |                               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from horses.cpp:2:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
horses.cpp:37:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   37 |                 if(l%2==1)ans=max(ans,sty[l++]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
horses.cpp:37:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   37 |                 if(l%2==1)ans=max(ans,sty[l++]);
      |                               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
horses.cpp:37:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   37 |                 if(l%2==1)ans=max(ans,sty[l++]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
horses.cpp:37:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   37 |                 if(l%2==1)ans=max(ans,sty[l++]);
      |                               ~~~^~~~~~~~~~~~~~
horses.cpp:38:34: error: no matching function for call to 'max(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
   38 |                 if(r%2==0)ans=max(ans,sty[r--]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
horses.cpp:38:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   38 |                 if(r%2==0)ans=max(ans,sty[r--]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
horses.cpp:38:34: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   38 |                 if(r%2==0)ans=max(ans,sty[r--]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
horses.cpp:38:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   38 |                 if(r%2==0)ans=max(ans,sty[r--]);
      |                               ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
horses.cpp:38:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   38 |                 if(r%2==0)ans=max(ans,sty[r--]);
      |                               ~~~^~~~~~~~~~~~~~
horses.cpp: In function 'll resi()':
horses.cpp:79:23: error: 'a' was not declared in this scope
   79 |         ans=(ans*getx(a+1,n-1))%MOD;
      |                       ^